[noip2015 pjt3]求和

思维题

把给定式子拆掉（分配律），前缀和维护

注意long long！！！

注意%%%%%%！！！

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 #define maxn 100233
 6 #define maxm 100233
 7 #define ll long long
 8 const ll MOD=10007;
 9 ll n,m;
10 ll ans=0;
11 ll num[maxn],col[maxn];
12 ll cnt[maxm][2],number[maxm][2],rSum[maxm][2],sum[maxm][2];
13 //cnt:同颜色同奇偶的个数；
14 //number:序号的前缀和；sum:数字的前缀和；rSum:序号*数字的前缀和；
15 int main(){
16     scanf("%lld%lld",&n,&m);
17     for (ll i=1;i<=n;i++) scanf("%lld",&num[i]);
18     for (ll i=1;i<=n;i++) scanf("%lld",&col[i]);
19     for (ll i=1;i<=n;i++){
20         ll c=col[i],x=i%2;
21         cnt[c][x]++;
22         if (cnt[c][x]>1) {
23             ans+=(number[c][x]*num[i]%MOD+rSum[c][x]+(cnt[c][x]-1)*i*num[i]%MOD
24             +i*sum[c][x]%MOD)%MOD;
25         }
26         ans%=MOD;
27         number[c][x]=(number[c][x]+i)%MOD;
28         rSum[c][x]=(rSum[c][x]+i*num[i])%MOD;
29         sum[c][x]=(sum[c][x]+num[i])%MOD;
30     }
31     printf("%lld
",ans);
32     return 0;
33 }

View Code