检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。
题面
题目描述
维护一个正整数多重集合 ,初始为空,支持两个操作:
- 插入:插入一个新数 ;
- 修改:令集合中所有数加 。
每次操作结束后,输出 中所有数的 次方和, 预先给定,对 取模。
输入格式
第一行两个数 ,其中 表示操作次数。
接下来 行,每行可能为以下两种之一:
0 x
,表示插入一个大小为 的新元素。1
,表示令集合 里所有数加一。
输出格式
输出 行,第 行表示第 次操作结束之后, 中所有数的 次方和。
样例输入输出
样例输入 #1
3 2
0 1
0 1
1
样例输出 #1
1
2
8
数据范围与约定
对于 的数据,,,。
思路
这道题考场上大家都是直接把二项式定理拿出来用 A 掉的,复杂度是 ,可惜就我一个菜鸡把二项式定理忘掉了,所以通过杨辉三角手推完二项式定理之后顺带着出来了一种 的做法。可惜的是考场上忘记处理负数取模的问题导致猛挂到 20 分。下面带来我的考场思路,可能会有些许罗嗦:
首先题目要求在每次操作完成后输出多重集合 中所有数的 次方和,因此可以从这里下手。
插入操作的数的 次方可以直接加进全局和中,因此只需要考虑如何处理全局加 的问题即可。
先写出一些加 后 次方和的式子进行观察:
-
当 时,
-
当 时,
-
当 时,
-
当 时,
可以观察到系数呈现出了杨辉三角的形式:
那么可以考虑记录全局累计增加的数 ,然后每次全局加之后都将 ,再重新计算全局和。此时需要将新插入的数 作为 存入以便计算。
现在再来看一看 的问题,有一种想法是可以将其按照 的形式递归展开,比如 就可以这样展开:
当 时,系数分布如下图所示:
推广得:
举个稍大一些的例子:
设左对齐的杨辉三角的第 行第 列上的数为 ,那么可以将总和记为:
显然 可以使用前缀和优化到 ,记为 ,最终形式为:
复杂度为 。
代码
#include <iostream>
using std::cin;
using std::cout;
const char endl = '\n';
const int N = 2e5 + 5,
K = 55;
const int mod = 1e9 + 7;
int m, k, d, cnt;
long long f[K][K], s[K], sum;
long long binpow(long long a, long long b) {
a %= mod;
long long res = 1;
while (b) {
if (b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
int main() {
std::ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> m >> k;
f[0][0] = 1;
for (int i = 1; i <= k; i++) {
f[i][0] = 1;
for (int j = 1; j <= i; j++) {
f[i][j] = (f[i - 1][j - 1] + f[i - 1][j]) % mod;
}
}
while (m--) {
int op;
cin >> op;
if (op == 0) {
int x;
long long p = 1;
cin >> x;
s[0] = (s[0] + 1) % mod;
for (int i = 1; i <= k; i++) {
p = (p * (x - d) % mod + mod) % mod;
s[i] = (s[i] + p) % mod;
}
sum = (sum + binpow(x, k)) % mod;
} else { // op == 1
d++;
sum = 0;
for (int i = 0; i <= k; i++) {
sum = (sum + f[k][i] * binpow(d, i) % mod * s[k - i] % mod) % mod;
}
}
cout << sum << endl;
}
return 0;
}