题意:
给你一个a数组和一个w数组,定义
请你求 的值?
思路:
由于n<=5 * 10^5,所以暴力肯定是不行的,所以我们可以按暴力求法列出式子看是否能优化。
当n=5时,结果=f(1,1)+f(1,2)+f(1,3)+f(1,4)+f(1,5)+f(2,2)+f(2,3)+f(2,4)+f(2,5)+f(3,3)+f(3,4)+f(3,5)+f(4,4)+f(4,5)+f(5,5);
f(1,1)+f(2,2)+f(3,3)+f(4,4)+f(5,5)=w1 * (a1+a2+a3+a4+a5);
f(1,2)+f(2,3)+f(3,4)+f(4,5)=w2 * (a1+2(a2+a3+a4)+a5);
f(1,3)+f(2,4)+f(3,5)=w3 * (a1+2a2+3a3+2a4+a5);
f(1,4)+f(2,5)=w4 * (a1+2(a2+a3+a4)+a5);
f(1,5)=w5 * (a1+a2+a3+a4+a5);
相信聪明的你已经看出来了,我们对a数组进行求前缀和数组sum。
再对a数组在(i<=n/2)时按sum1[i]=sum1[i-1]+i *(a[i]+a[n-i+1])的方式进行求sum1数组。
然后就可以用O(n)的时间求出结果了。
代码:
#include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #define inf 1000000007 #define eps 0.00000001 using namespace std; typedef long long ll; typedef unsigned long long ull; const int maxn=100005; inline int read() { char c=getchar(); int f=1, x=0; while(c>'9'||c<'0') { if(c=='-') { f=-1; } c=getchar(); } while(c<='9'&&c>='0') { x=(x<<3)+(x<<1)+(c^48); c=getchar(); } return f*x; } ll a[300005], w[300005], sum[300005], sum1[300005]; int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%lld",&a[i]); sum[i]=sum[i-1]+a[i]; } for(int i=1;i<=n;i++) { scanf("%lld",&w[i]); } ll ji=0, z=0; for(int i=1;i<=n/2;i++) { sum1[i]=(sum1[i-1]+i*a[i]+i*a[n-i+1])%inf; } for(int i=1;i<=n;i++) { int p=i; if(p>n/2) { p=n-p+1; } z=(z+(w[i]*(p*((sum[n-p+1]-sum[p-1])%inf)%inf+sum1[p-1])%inf)%inf)%inf; } cout << z << endl; return 0; }