P2671 [NOIP 2015 普及组] 求和
题目描述
一条狭长的纸带被均匀划分出了 \(n\) 个格子,格子编号从 \(1\) 到 \(n\)。每个格子上都染了一种颜色 \(color_i\) 用 \([1,m]\) 当中的一个整数表示),并且写了一个数字 \(number_i\)。
编号 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|
颜色和数字 | \(\color{blue}{5}\) | \(\color{blue}{5}\) | \(\color{red}{3}\) | \(\color{red}{2}\) | \(\color{blue}{2}\) | \(\color{red}{2}\) |
定义一种特殊的三元组:\((x,y,z)\),其中 \(x,y,z\) 都代表纸带上格子的编号,这里的三元组要求满足以下两个条件:
-
\(x,y,z\) 都是整数,\(x<y<z,y-x=z-y\)。
-
\(color_x=color_z\)。
满足上述条件的三元组的分数规定为 \((x+z) \times (number_x+number_z)\)。整个纸带的分数规定为所有满足条件的三元组的分数的和。这个分数可能会很大,你只要输出整个纸带的分数除以 \(10007\) 所得的余数即可。
输入格式
第一行是用一个空格隔开的两个正整数 \(n\) 和 \(m,n\) 表纸带上格子的个数,\(m\) 表纸带上颜色的种类数。
第二行有 \(n\) 用空格隔开的正整数,第 \(i\) 个数字表示纸带上编号为 \(i\) 格子上面写的数字 \(number_i\)。
第三行有 \(n\) 用空格隔开的正整数,第 \(i\) 数字表示纸带上编号为 \(i\) 格子染的颜色 \(color_i\)。
输出格式
一个整数,表示所求的纸带分数除以 \(10007\) 所得的余数。
输入输出样例 #1
输入 #1
6 2
5 5 3 2 2 2
2 2 1 1 2 1
输出 #1
82
输入输出样例 #2
输入 #2
15 4
5 10 8 2 2 2 9 9 7 7 5 6 4 2 4
2 2 3 3 4 3 3 2 4 4 4 4 1 1 1
输出 #2
1388
说明/提示
样例 1 解释
纸带如题目描述中的图所示。
所有满足条件的三元组为:\((1, 3, 5), (4, 5, 6)\)。
所以纸带的分数为 \((1 + 5) \times (5 + 2) + (4 + 6) \times (2 + 2) = 42 + 40 = 82\)。
对于第 \(1\) 组至第 \(2\) 组数据, \(1 ≤ n ≤ 100, 1 ≤ m ≤ 5\);
对于第 \(3\) 组至第 \(4\) 组数据,\(1 ≤ n ≤ 3000, 1 ≤ m ≤ 100\);
对于第 \(5\) 组至第 $ 6 $ 组数据,\(1 ≤ n ≤ 100000, 1 ≤ m ≤ 100000\),且不存在出现次数超过 $ 20 $ 的颜色;
对于全部 \(10\) 组数据,\(1 ≤ n ≤ 100000, 1 ≤ m ≤ 100000, 1 ≤ color_i ≤ m,1≤number_i≤100000\)。
题解
首先,我们可以观察到分数是只与\(x\)和\(z\)有关。
那么我们便可以忽略掉\(y\)
那么要求就从枚举三元组变为了枚举二元组且\(z-x\)不能被\(2\)整除
那就可以发现\(x,z\)的奇偶性相同
那么朴素的方法就是枚举\(x,z\),
时间复杂度为\(O(n^2)\),
无法通过这道题的所有数据。
那让我们再把目光看回到答案式子,
\((x+z)\times(number_x+number_z)\)
可以用乘法分配律将其拆开,
得\(x\times(number_x+number_z)+z\times(number_x+number_z)\)
那么显然可以维护颜色为\(i\),奇偶性为\(j\)的\(number\)和\(sum_{i,j}\),格子个数\(size_{i,j}\)
则那么对于每个格子\(x\),对答案的贡献就是\(i \times (sum_{i,j}-number_i) + i \times number_i \times (size_{i,j}-1)\)
化简式子,得\(i \times sum_{i,j}+i \times (size_{i, j} - 2) \times number_i\)
Code:
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7, mod = 10007;
int n, m;
int color[N], number[N];
long long sum[N][2], sz[N][2], ans;
inline int read(){int sum = 0, f = 1;char c = getchar_unlocked();while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar_unlocked();}while(c >= '0' && c <= '9'){sum = (sum << 3) + (sum << 1) + (c - 48);c = getchar_unlocked();}return sum * f;
}
int main(){n = read();m = read();for(int i = 1; i <= n; i++){number[i] = read() % mod;}for(int i = 1; i <= n; i++){color[i] = read();sum[color[i]][i & 1] = (sum[color[i]][i & 1] + number[i]) % mod;sz[color[i]][i & 1]++;}for(int i = 1; i <= n; i++){int c = color[i], op = i & 1;ans = (ans + i * sum[c][op] % mod + (sz[c][op] - 2) * i * number[i] % mod ) % mod;}printf("%lld\n", ans);return 0;
}
//最优解前10ヾ(≧▽≦*)o