题解 CF407C 【Curious Array】
MILLOPE
2019-07-12 20:08:56
## 写在前面
既然没有人写题解，那么我这个蒟蒻就写一篇水题解好了
[我的博客qwq](https://blog.csdn.net/qq_34493840/article/details/95515653)
## 题目
给出$n$个数，有$m$个操作，每个操作是将$[L,R]$之间的数加上$C(j-L+k,k)$，$L<=j<=R$最后输出这$n$个数的值。
## 题解
- ~~虽然我考场上推出了式子但是我还是打的n^2^暴力（暴力选手qwq~~
- n阶差分可能有点难以理解可以先看一下[三步必杀（二阶差分](https://www.luogu.org/problemnew/show/P4231)
- [三步必杀题解](https://blog.csdn.net/qq_34493840/article/details/94474399)
- 我们要加的序列
$$\dbinom{k}{k},\dbinom{k+1}{k}\cdots\dbinom{r-l+k}{k}$$
- 又可以写成
$$\dbinom{k}{0},\dbinom{k+1}{1}\cdots\dbinom{r-l+k}{r-l}$$
- 结合公式
$$\dbinom{n}{m}=\dbinom{n-1}{m}+\dbinom{n-1}{m-1}$$
- 该序列的一阶差分序列为
$$\dbinom{k-1}{0},\dbinom{k}{1}\cdots\dbinom{r-l+k-1}{r-l}\Leftrightarrow\dbinom{k-1}{k-1},\dbinom{k}{k-1}\cdots\dbinom{r-l+k-1}{k-1}$$
- 二阶差分序列
$$\dbinom{k-2}{0},\dbinom{k-1}{1}\cdots\dbinom{r-l+k-2}{r-l}\Leftrightarrow\dbinom{k-2}{k-2},\dbinom{k-1}{k-2}\cdots\dbinom{r-l+k-2}{k-2}$$
- $j$阶差分序列
$$\dbinom{k-j}{0},\dbinom{k-j+1}{1},\cdots,\dbinom{r-l+k-j}{r-l}\Leftrightarrow\dbinom{k-j}{k-j},\dbinom{k-j+1}{k-j}\cdots\dbinom{r-l+k-j}{k-j}$$
- 我们可以发现这样的组合数序列在进行$k+1$次差分后全部变为$0$，我们可以在$k+1$次差分序列的$l$位置加上$1$，在$r+1$位置减去前面的前缀和即可
- 而$j$阶差分的前$k$位的和等于$j-1$阶差分序列的第$k$个数（~~手推一下吧~~
- 所以第$j$阶序列的前缀和
$$\sum_{j=0}^k\dbinom{r-l+k-j}{r-l}=\dbinom{r-l+k-j+1}{k-j+1}$$
- 每次消除前缀和对后面的影响即可
## $code$
```cpp
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100000 + 1000;
const int maxm = 100 + 10;
const int mod = 1000000007;
typedef long long LL;
template <class T>
inline void read(T &s) {
s = 0;
T w = 1, ch = getchar();
while (!isdigit(ch)) { if (ch == '-') w = -1; ch = getchar(); }
while (isdigit(ch)) { s = (s << 1) + (s << 3) + (ch ^ 48); ch = getchar(); }
s *= w;
}
int n, m;
LL a[maxn];
LL c[maxn][maxm], ans[maxn][maxm];
void init() {
c[0][0] = 1;
for (int i = 1; i < maxn; ++i) {
c[i][0] = 1;
for (int j = 1; j <= i && j < maxm; ++j) {
c[i][j] = (c[i-1][j-1] + c[i-1][j]) % mod;
}
}
}
int main() {
freopen("data.in", "r", stdin);
freopen("bf.out", "w", stdout);
init();
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
int l, r, k;
while (m--) {
scanf("%d %d %d", &l, &r, &k);
for (int i = 0; i <= k; ++i)
ans[l][i] = (ans[l][i] + c[k][k-i]) % mod;
for (int i = 0; i <= k; ++i)
ans[r+1][i] = (ans[r+1][i] - c[r-l+k+1][k-i]) % mod;
}
for (int i = 1; i < n; ++i) {
for (int j = 101; j >= 1; --j) {
ans[i+1][j-1] = (ans[i+1][j-1] + ans[i][j] + ans[i][j-1]) % mod;
}
}
for (int i = 1; i <= n; ++i) {
printf("%lld ", ((ans[i][0] + a[i]) % mod + mod) % mod);
}
return 0;
}
```