JZOJ5922. 【NOIP2018模拟10.23】sequence

题意：

小 F 是一位 Hack 国的居民，他生活在一条长度为 n 的街道上，这个街道上总共有 n 个商店。每个商店里售卖着不同的 Hack 技能包，每个商店本身也会有个便利值。初始时，每个商店的便利值均为 0。每一天，街道上都会有一些商店优化改造。
具体来说，对于每一天，优化改造的商店都是一个连续的区间 l ∼ r，每次优化改造也会有一个优化参数 k。对于所有 l ≤ i ≤ r ，第 i 个商店的便利值会增加。

小 F 想知道，m 天之后，每个商店的便利值分别是多少。由于小 F 并不喜欢高精度，因此你只需要输出便利值对 10^9 + 7 取模的结果。

数据范围：

Analysis：

可以根据杨辉三角的递推式：$C_i^j=C_{i-1}^{j-1}+C_i^{j-1}$Cij​=Ci−1j−1​+Cij−1​。
发现这个东西可以分为$k$k层逐层做，每一次相当于做一次前缀和。我们搞一个差分把区间边界的影响消掉，发现他们$k$k是不同的，这样很难做，某一部分重复算。考虑对于每一个$k$k做一次，复杂度$O(nk^2)$O(nk2)。或者我们从高往低做，让他顶住最下面。复杂度:$O(nk)$O(nk)

Code：

# include<cstdio>
# include<cstring>
# include<algorithm>
using namespace std;
const int N = 6e5 + 5;
const int mo = 1e9 + 7;
typedef long long ll;
int inv[N],fac[N],fac_[N],tag[N][25];
int n,m;
inline int read()
{
	int x = 0; char ch = getchar();
	for (; ch < '0' || ch > '9' ; ch = getchar());
	for (; ch >= '0' && ch <= '9' ; ch = getchar()) x = x * 10 + ch - '0';
	return x;
}
inline int inc(int x,int y) { return x + y >= mo ? x + y - mo : x + y; }
inline int dec(int x,int y) { return x - y < 0 ? x - y + mo : x - y; }
inline int C(int n,int m) { return (ll)fac[n] * fac_[m] % mo * fac_[n - m] % mo; }
int main()
{
	freopen("sequence.in","r",stdin);
	freopen("sequence.out","w",stdout);
	n = read(),m = read(); fac[0] = fac_[0] = inv[1] = 1;
	for (int i = 1 ; i <= n + 20 ; ++i)
	{
		if (i > 1) inv[i] = (ll)(mo - mo / i) * inv[mo % i] % mo;
		fac[i] = (ll)fac[i - 1] * i % mo,fac_[i] = (ll)fac_[i - 1] * inv[i] % mo;
	}
	for (int i = 1 ; i <= m ; ++i)
	{
		int l = read(),r = read(),k = read();
		++tag[l][k + 1],tag[r + 1][k + 1] = dec(tag[r + 1][k + 1],1);
		for (int j = k ; j ; --j) tag[r + 1][j] = dec(tag[r + 1][j],C(r - l + k - j + 1,k - j + 1));
	}
	for (int j = 21 ; j ; --j)
		for (int i = 1 ; i <= n ; ++i) tag[i][j] = inc(tag[i][j],inc(tag[i][j + 1],tag[i - 1][j]));
	for (int i = 1 ; i <= n ; ++i) printf("%d\n",tag[i][1]);
	return 0;
}