• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

Recommended Posts

PART 1: 题目大意

设$s(l,r)=\ sum _ { I=l}^{r} a _ I \乘以b_i美元,求$\sum_{l=1}{n}\sum_{r=1}{n} s(l,r)$

PART 2:解题思路

从数据范围可以看出来,这是一道思维题,我没需要把体面给出的柿子通过转化使其复杂度下降。从数据范围看出,这里需要时间复杂度大约十美元。

不妨先把题目给的柿子拆开来看是否存在规律:

$ $ ans=a _ 1 \ times(\ sum _ { I=1}^{n} b _ I \ sum _ { I=1}^{n-1} b _ I \ sum _ { I=1}^{n-2} b _ I……\ sum _ { I=1}^{1} b _ I)\ a _ 2 \ times(\ sum _ { I=1}^{n} b _ I \ sum _ { I=1}^{n-1} b _ I \ sum _ { I=1}^{n-2} b _ I……) sum _ { I=1}^{2} b _ I \ sum _ { I=2 } { n } b _ I \ sum _ { I=2 } { I=2 } { n

设$a_m$美元美元对应的括号中的柿子为百万美元,则:

$ $ f(m)=\ sum _ { I=1}^{n} b _ I \ sum _ { I=1}^{n-1} b _ I \ sum _ { I=1}^{n-2} b _ I……\ sum _ { I=2}^{n} b _ I \ \ sum _ { I=2}^{n-1} b _ I \ sum _ { I=2}^{n-2} b _ I……\ sum _ { I=2}^{m} b _ I \……\ \ sum _ { I=m } { n } b _ I \ sum _ { I=m } { n-1 } b _ I \ sum _ { I=I

这样看上去貌似没有什么规律,我们举两个例子来看

$ $ f(1)=\ sum _ { I=1}^{n} b _ I \ sum _ { I=1}^{n-1} b _ I \ sum _ { I=1}^{n-2} b _ I……\ sum _ { I=1}^{1} b _ I=\ sum _ { I=1}^n b _ I \ times(n-I 1)$ $

$ $ f(2)=\ sum _ { I=1}^{n} b _ I \ sum _ { I=1}^{n-1} b _ I \ sum _ { I=1}^{n-2} b _ I……\ sum _ { I=2}^{n} b _ I \ sum _ { I=2}^{n-1} b _ I \ sum _ { I=2}^{n-2} b _ I……\ sum _ { I=2}^{2} b _ I \=\ sum _ { I=1 } n b _ I \ times(n-I 1)-b _ 1 \ sum _ { I=2 } n b _ I \ n

$$……$$

感觉他们都有很相似的$\sum_{i=k}^n b_i \times (n-i 1)$这部分,不妨设$ sum=\ sum _ { I=1}^n b _ I \ times(n-I 1)$,再用美元总和美元将其替换,那么会得到:

$$f(1)=sum$$

$ $ f(2)=2 sum-(n ^ 1)b _ 1 $ $

$ $ f(3)=3 sum-2(n-1)b _ 1-(n-1)b _ 2 $ $

以此类推,那么得到:

$ $ f(m)=m \乘以总和-\sum_{i=1}^{m-1}(n 1)B1 \乘以(m-i)$$

这样的柿子是$O(n^2)$的,于是我们就拿到了70美分的分数,代码如下:

#includebits/stdc .h

#定义MAXN 500010

#定义1000000007年11月

使用命名空间标准

typedef long long ll

int n;

ll a[MAXN],b[MAXN],sum,ans

int main(){

//freopen('sum.in ',' r ',stdin);

//freopen('sum.out ',' w ',stdout);

scanf('%d ',n);

for(int I=1;I=n;i ) scanf('%lld ',a),a%=MOD;

for(int I=1;I=n;i ) scanf('%lld ',b),b%=MOD;

for(int I=1;I=n;I)sum=(n-I个^ 1)* b,sum %=MOD

for(int I=1;I=n;i ){

ll tmp=(sum * I)% MOD;

for(int j=1;j I;j)tmp=(tmp-((((b[j]*(n ^ 1))% mod)*(I-j))% mod)mod)% mod;

ans=(ans tmp * a)% MOD;

}

printf('%lld\n ',ans);

返回0;

}

那么如何才能拿到满分呢?考虑把刚刚推出来的柿子进一步优化。观察发现,将柿子中的求和项裂开来,得到:

$ $ f(m)=m \乘以sum-(n 1)(m\sum_{i=1}^{m-1}b_i-\ sum _ { I=1}^{m-1 } b _ I \乘以i)$$

可以预处理出$b_i$美元美元以及$ b _ i \乘以一美元的前缀和,将柿子优化到$O(n)$,于是得到了接受的$美元的代码:

#includebits/stdc .h

#定义MAXN 500010

#定义1000000007年11月

使用命名空间标准

typedef long long ll

ll n;

ll sum,ans

ll a[MAXN],b[MAXN],sum_b[MAXN],sum _ mult _ b[MAXN];

int main(){

//freopen('sum.in ',' r ',stdin);

//freopen('sum.out ',' w ',stdout);

scanf('%lld ',n);

for(ll I=1;I=n;i ) scanf('%lld ',a),a%=MOD;

for(ll I=1;I=n;i ) scanf('%lld ',b),b%=MOD;

for(ll I=1;I=n;i ){

sum _ b=(sum _ b[I-1]b)% MOD;

sum _ mult _ b=(sum _ mult _ b[I-1](b* I)% MOD)% MOD;

}

for(ll I=1;I=n;I)sum=(n-I个^ 1)* b,sum %=MOD

for(ll I=1;I=n;i ){

ll tmp=((sum * I)% mod-((n ^ 1)*(((I * sum _ b[I-1])% mod-sum _ mult _ b[I-1]mod)% mod mod)% mod mod;

ans=(ans(tmp * a)% mod)% mod;

}

printf("% lld \ n ",年):

返回0;

}

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now