洛谷P2671 求和
数学 公式转化 前缀和
题意 设三元组 x y z 要求 x < y < z y-x = z-y
且要求 color[ x ] == color[ z ]
比如说 求当前是 z 那么之前的 x 对 这个答案的贡献
设满足条件 的有count 个 分别 为 x1 x2 x3 x4
贡献为 (x1+z)*(num1+numz)+(x2+z)*(num2+z)+(x3+z)*(num3+numz) ....
答案 = x1*num1+x1numz+znum1+znumz +...
= sigama(xi*numi) + sigama(xi)*numz + siagma(numi)*z+ count *z*numz 公式
这样就只要记录一下每一个符合条件的 前缀和
用着个前缀来更新答案就行了 不过要注意要经常取mod
求所有符合条件的三元组的 价值总和
其实我们发现只有 x z 奇偶性相同时才能累加上去
我们开一个前缀 s[ t ][ c ][ ] 表示 奇偶性为 t ，颜色 为 c 的累加上去
0 表示 这样数的个数 count
1 表示 sigama(xi)
2 表示 sigama(numi)
3 表示 sigama(xi * numi)
然后套在公式上就行了
1 #include <cstdio> 2 #include <cmath> 3 #include <cstdlib> 4 #include <cstring> 5 #include <string> 6 #include <algorithm> 7 #include <iostream> 8 #include <iomanip> 9 #define ll long long 10 using namespace std ; 11 12 const ll maxn = 100011,mod = 10007 ; 13 int n,m,ans ; 14 int number[ maxn ],color[ maxn ],s[2][maxn][4] ; 15 16 inline ll read() 17 { 18 char ch = getchar() ; 19 int x = 0,f =1 ; 20 while(ch<'0'||ch>'9') { if(ch=='-') f = -1 ; ch = getchar() ; } 21 while(ch>='0'&&ch<='9') {x = x*10 + ch - 48 ; ch = getchar() ; } 22 return x * f ; 23 } 24 25 inline void init() 26 { 27 n = read() ; m = read() ; 28 for(int i=1;i<=n;i++) number[ i ] = read(),number[ i ] %= mod ; 29 for(int i=1;i<=n;i++) color[ i ] = read() ; 30 } 31 32 inline void work() 33 { 34 ans = 0 ; 35 for(int i=1;i<=n;i++) 36 { 37 int t = i%2,c = color[ i ],z = i% mod ,numz = number[ i ] % mod ; 38 int count = s[t][c][0] ,sumx = s[t][c][1],sumnum = s[t][c][2],sumx_num = s[t][c][3] ; 39 ans = ( ans + count * z % mod *numz % mod ) % mod ; 40 ans = ( ans + sumx*numz % mod) % mod ; 41 ans = ( ans + sumnum * z % mod ) %mod ; 42 ans = ( ans + sumx_num ) % mod ; 43 s[t][c][0]++ ; s[t][c][0] %=mod ; 44 s[t][c][1]+=z ; s[t][c][1] %=mod ; 45 s[t][c][2]+=numz; s[t][c][2] %=mod ; 46 s[t][c][3]+=z*numz % mod ; s[t][c][3] %=mod ; 47 } 48 } 49 50 inline void output() 51 { 52 printf("%d ",ans) ; 53 } 54 55 int main() 56 { 57 init() ; 58 work() ; 59 output() ; 60 return 0 ; 61 }