一条狭长的纸带被均匀划分出了 n n n个格子,格子编号从 1 1 1到 n n n。每个格子上都染了一种颜色 c o l o r i color_i colori 用 [ 1 , m ] [1,m] [1,m]当中的一个整数表示),并且写了一个数字 n u m b e r i number_i numberi。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ieUYI0vp-1636554354924)(1829-2364231.png)]
定义一种特殊的三元组: ( x , y , z ) (x,y,z) (x,y,z),其中 x , y , z x,y,z x,y,z都代表纸带上格子的编号,这里的三元组要求满足以下两个条件:
满足上述条件的三元组的分数规定为 ( x + z ) × ( n u m b e r x + n u m b e r z ) (x+z) \times (number_x+number_z) (x+z)×(numberx+numberz)。整个纸带的分数规定为所有满足条件的三元组的分数的和。这个分数可能会很大,你只要输出整个纸带的分数除以 10 , 007 10,007 10,007所得的余数即可。
第一行是用一个空格隔开的两个正整数 n n n 和 m , n m,n m,n 表纸带上格子的个数, m m m表纸带上颜色的种类数。
第二行有 n n n用空格隔开的正整数,第 i i i数字 n u m b e r number number表纸带上编号为 i i i格子上面写的数字。
第三行有 n n n用空格隔开的正整数,第 i i i数字 c o l o r color color表纸带上编号为 i i i格子染的颜色。
一个整数,表示所求的纸带分数除以1000710007所得的余数。
则不难看出 x + z = 2 ∗ y x+z = 2*y x+z=2∗y ,需要x与z的奇偶性与颜色一致,在读入数据时可以根据此分类。
设每个分类得出的部分有k个数,每个数下标分别为 x [ 1 ] , x [ 2 ] , . . . , x [ k ] x[1],x[2],...,x[k] x[1],x[2],...,x[k] ,在number数组中的值为 y [ 1 ] , y [ 2 ] , . . . , y [ k ] y[1],y[2],...,y[k] y[1],y[2],...,y[k] ,那么该分类部分对答案的贡献为
Δ a n s = ( x [ 1 ] + x [ 2 ] ) ∗ ( y [ 1 ] + y [ 2 ] ) + ( x [ 1 ] + x [ 3 ] ) ∗ ( y [ 1 ] + y [ 3 ] ) + . . . + ( x [ 1 ] + x [ k ] ) ∗ ( y [ 1 ] + y [ k ] ) + ( x [ 2 ] + x [ 3 ] ) ∗ ( y [ 2 ] + y [ 3 ] ) + . . . . ( x [ 2 ] + x [ k ] ) ∗ ( y [ 2 ] + y [ k ] ) + ( x [ k − 1 ] + x [ k ] ) ∗ ( y [ k − 1 ] + y [ k ] ) \Delta ans = \\ \quad (x[1]+x[2])*(y[1]+y[2])+(x[1]+x[3])*(y[1]+y[3])+...+(x[1]+x[k])*(y[1]+y[k])\\\,+(x[2]+x[3])*(y[2]+y[3])+....(x[2]+x[k])*(y[2]+y[k])\\\ +(x[k-1]+x[k])*(y[k-1]+y[k]) Δans=(x[1]+x[2])∗(y[1]+y[2])+(x[1]+x[3])∗(y[1]+y[3])+...+(x[1]+x[k])∗(y[1]+y[k])+(x[2]+x[3])∗(y[2]+y[3])+....(x[2]+x[k])∗(y[2]+y[k]) +(x[k−1]+x[k])∗(y[k−1]+y[k])
对x[i]运用分配率得
= ( ∑ i = 1 k − 1 ∑ j = i + 1 k x [ i ] ∗ ( y [ i ] + y [ j ] ) ) + ( ∑ j = 2 k ∑ i = 1 j − 1 x [ j ] ∗ ( y [ i ] + y [ j ] ) ) = (\sum_{i=1}^{k-1}\sum_{j=i+1}^{k} x[i]*(y[i]+y[j]))\\ + (\sum_{j=2}^{k}\sum_{i=1}^{j-1}x[j]*(y[i]+y[j])) =(∑i=1k−1∑j=i+1kx[i]∗(y[i]+y[j]))+(∑j=2k∑i=1j−1x[j]∗(y[i]+y[j]))
= ∑ i = 1 k x [ i ] ( ∑ j = i + 1 k ( y [ i ] + y [ j ] ) + ∑ j = 1 i − 1 ( y [ j ] + y [ i ] ) ) =\sum_{i=1}^{k}x[i](\sum_{j=i+1}^{k}(y[i]+y[j])+\sum_{j=1}^{i-1}(y[j]+y[i])) =∑i=1kx[i](∑j=i+1k(y[i]+y[j])+∑j=1i−1(y[j]+y[i]))
= ∑ i = 1 k x [ i ] ( ∑ j = 1 k y [ j ] + ( k − 2 ) y [ i ] ) =\sum_{i=1}^{k}x[i](\sum_{j=1}^{k}y[j]+(k-2)y[i]) =∑i=1kx[i](∑j=1ky[j]+(k−2)y[i])
其中, ∑ j = 1 k y [ j ] \sum_{j=1}^{k}y[j] ∑j=1ky[j] 为定值,可以用前缀和解决
总复杂度 O ( n ) O(n) O(n)
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define MOD 10007 #define intmax 2147483647 #define memmax 0x7fffffff inline ll read() { ll x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();} return x*f; } ll n, m; ll number[100005], color[100005]; ll noof[100005][2], pre[100005][2]; ll ans; void solve() { n = read(), m = read(); for(int i=1; i<=n; i++) { number[i] = read(); } for(int i=1; i<=n; i++) { color[i] = read(); // 统计当前分类容器数量 noof[color[i]][i%2]++; // 前缀number[i]的和 pre[color[i]][i%2] = (pre[color[i]][i%2] + number[i]) %MOD; } for(int i=1; i<=n; i++) { // (noof[color[i]][i%2]-2) == n-2 // i == x[i] // number[i] == y[i] ans = (ans + (i * ((noof[color[i]][i%2]-2)*number[i] %MOD + pre[color[i]][i%2]) ) ) %MOD; } cout << ans << endl; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); solve(); }