$ >Codeforces space 408 E. Curious Array<$
题目大意 :
有一个长度为 (n) 的序列 (a) ，(m) 次操作，每一次操作给出 (l, r, k) ，使得 (i in[l, r]) 加上 (i-l+kchoose k) ，求 (m) 次操作后的序列(1 leq n, m leq 10^5, 0 leq k leq 100)
解题思路 :
观察发现这个操作是加上 (C_{k+i}^{k}) 这样的东西，根据组合数的递推公式 $C_{n}^{m} = C_{n-1}^{m} + C_{n-1}^{m-1} $ 可以得知，操作的本质是加上对 ((1,1,1...1) (r-l+1)) 个 (1) 这个序列做 (k) 次前缀和后的结果。
所以可以把序列分成 (k) 层来处理，每一次操作在第 (k) 层的 (l) 位置加上 (1) ，全部做完之后对从高到低对每一层做前缀和，下一层加上上一层对应位置的前缀和即可。但是还要在 (r+1) 处减去贡献，考虑 (k) 次前缀和的贡献会对其下面所有层产生影响，不难发现此时第 (k-i) 层要被减掉的贡献是做 (i) 次前缀和前 (r-l+1) 项的和，对应回原来的组合数减去即可。
/*program by mangoyang*/
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<bits/stdc++.h>
#define inf (0x7f7f7f7f)
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
typedef long long ll;
using namespace std;
template <class T>
inline void read(T &x){
int f = 0, ch = 0; x = 0;
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;
for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
if(f) x = -x;
}
#define int ll
const int N = 200005, Mod = 1e9+7;
int js[N], inv[N], a[N][105], n, m;
inline int Pow(int a, int b){
int ans = 1;
for(; b; b >>= 1, a = 1ll * a * a % Mod)
if(b & 1) ans = 1ll * ans * a % Mod;
return ans;
}
inline int C(int x, int y){ return js[x] * inv[y] % Mod * inv[x-y] % Mod; }
signed main(){
js[0] = inv[0] = 1;
for(int i = 1; i < N; i++)
js[i] = 1ll * js[i-1] * i % Mod, inv[i] = Pow(js[i], Mod - 2);
read(n), read(m);
for(int i = 1; i <= n; i++) read(a[i][0]);
for(int i = 1, l, r, k; i <= m; i++){
read(l), read(r), read(k), a[l][k+1]++;
for(int j = 1; j <= k + 1; j++)
(a[r+1][j] -= C(r - l + k - j + 1, k - j + 1)) %= Mod;
}
for(int i = 101; i >= 0; i--){
int s = 0;
for(int j = 1; j <= n; j++){
(s += a[j][i+1]) %= Mod;
(a[j][i] += s) %= Mod;
}
}
for(int i = 1; i <= n; i++)
printf("%lld ", (a[i][0] % Mod + Mod) % Mod);
return 0;
}