5922. 【NOIP2018模拟10.23】sequence (File IO): input:sequence.in output:sequence.out
Time Limits: 1000 ms Memory Limits: 524288 KB Detailed Limits
Description
小 F 是一位 Hack 国的居民，他生活在一条长度为 n 的街道上，这个街道上总共有 n 个商店。每个商店里售卖着不同的 Hack 技能包，每个商店本身也会有个便利值。初始时，每个商店的便利值均为 0。每一天，街道上都会有一些商店优化改造。 具体来说，对于每一天，优化改造的商店都是一个连续的区间 l ∼ r，每次优化改造也会有一个优化参数 k。对于所有 l ≤ i ≤ r ，第 i 个商店的便利值会增加 
。 小 F 想知道，m 天之后，每个商店的便利值分别是多少。由于小 F 并不喜欢高精度，因此你只需要输出便利值对 10^9 + 7 取模的结果。
。 小 F 想知道，m 天之后，每个商店的便利值分别是多少。由于小 F 并不喜欢高精度，因此你只需要输出便利值对 10^9 + 7 取模的结果。 Input
从文件sequence.in中读入数据。 第 1 行，两个整数 n, m 表示街道的长度与天数。 接下来的 m 行，每行三个整数 l, r, k，表示第 i 天优化改造的商店区间和优化参数。
Output
输出到文件sequence.out中，共 n 行。 每行 1 个整数，表示第 i 个商店的便利值对 109 + 7 取模的结果。
Sample Input
5 31 4 32 5 03 4 2Sample 2见选手目录下的sequence/sequence2.in与sequence/sequence2.ans。该组样例的数据范围同第 1 个测试点。
Sample Output
1512241第 1 次操作之后，每个商店的便利值分别为 1, 4, 10, 20, 0。第 2 次操作之后，每个商店的便利值分别为 1, 5, 11, 21, 1。第 3 次操作之后，每个商店的便利值分别为 1, 5, 12, 24, 1。
做法（摘自JZOJ）：可以发现组合数有一个简单的性质，即 C(n k) = C(n−1 k) + C(n−1 k−1) ，我们可以从这 个式子中获得启发。考虑一个下标从 0 开始的数列，这个数列的每个数均为 1。 我们对这个数列做 k 阶前缀和。通过这个简单的式子，容易发现这个数列的第 i 项即为 C(k+i k ) 。于是我们可以得出一个这样的做法。 对于这个数列，维护这个数列的 k 阶差分。对于一次修改操作，我们只需要 在各阶差分数组上修改，最后做一遍 k 阶的前缀和即可。注意差分数组上修改 时，区间边界要相应地减掉一些值。时间复杂度 O(nk)，期望得分 100pts。
1 #include2 #include 3 #include 4 #include 5 #define LL long long 6 #define N 500010 7 #define rep(i,a,b) for(register int i=a;i<=b;++i) 8 #define dep(i,a,b) for(register int i=a;i>=b;--i) 9 using namespace std;10 LL mo=1e9+7;11 int n,m;12 LL f[22][N],a[N],ans[N];13 struct arr{14 int l,r,k;15 }e[N];16 17 bool cmp(arr x,arr y){18 return x.k>y.k;19 }20 21 int read(){22 int s=0;23 char ch=getchar();24 for(;ch<'0'||ch>'9';ch=getchar());25 for(;ch>='0'&&ch<='9';s=s*10+ch-'0',ch=getchar());26 return s;27 }28 29 int main(){30 freopen("sequence.in","r",stdin);31 freopen("sequence.out","w",stdout);32 n=read(),m=read();33 a[1]=1;34 rep(j,0,20)35 rep(i,1,n)36 a[i]=(a[i]+a[i-1])%mo,f[j][i]=a[i];37 rep(i,1,m) e[i].l=read(),e[i].r=read(),e[i].k=read();38 sort(e+1,e+m+1,cmp);39 int l=1;40 dep(i,e[1].k,0){41 while(l<=m&&e[l].k==i) ++ans[e[l].l],++l;42 rep(j,1,l-1) 43 ans[e[j].r+1]=(ans[e[j].r+1]-f[e[j].k-i][e[j].r-e[j].l+1])%mo;44 rep(j,1,n) 45 ans[j]=(ans[j]+ans[j-1]+mo)%mo;46 }47 rep(i,1,n) printf("%lld\n",ans[i]);48 }