Description
有m个区间加组合数操作，对于
l
≤
i
≤
r
l\leq i\leq r
l≤i≤r，给
a
i
a_i
ai加上
C
i
−
l
+
k
k
C_{i-l+k}^k
Ci−l+kk，
a
i
a_i
ai初始为0，
k
<
=
20
k<=20
k<=20。问最后所有
a
i
a_i
ai的值。
Solution
做法很多。 可以对
k
k
k分类，对于每个
k
k
k，执行区间加的一个区间
[
l
,
r
]
[l,r]
[l,r]的每个
i
i
i相当于加上一个关于
i
i
i的
k
k
k次多项式，我们把多项式的系数求出来，那么区间操作相当于将这些系数进行累加，可以用差分，在
l
l
l处打上这些系数，在
r
+
1
r+1
r+1减去，最后只用求前缀和即可。
其实我们发现，对于一个三元组
(
l
,
r
,
x
)
(l,r,x)
(l,r,x)，如果
r
=
n
r=n
r=n，我们开一个
k
×
n
k\times n
k×n的数组
b
b
b，在
b
k
,
l
b_{k,l}
bk,l上
+
1
+1
+1，最后向上向右做前缀和，
b
0
,
i
b_{0,i}
b0,i就是答案，可以理解成为一个从
(
k
,
l
)
(k,l)
(k,l)位置开始的向右上方的杨辉三角。对于
r
<
n
r<n
r<n我们只要在每个
b
i
,
r
+
1
b_{i,r+1}
bi,r+1减去相应的值即可。实际上就是维护k阶差分。
Code
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define fo(i,j,k) for(int i=j;i<=k;++i)
#define fd(i,j,k) for(int i=j;i>=k;--i)
using namespace std
;
typedef long long ll
;
const int N
=5e5+50,mo
=1e9+7;
ll c
[N
][22],b
[N
][22];
ll
pow(ll x
,int y
){
ll b
=1;
for(;y
;y
>>=1,x
=x
*x
%mo
) if(y
&1) b
=b
*x
%mo
;
return b
;
}
int main()
{
freopen("sequence.in","r",stdin);
freopen("sequence.out","w",stdout);
int n
,m
;
scanf("%d %d",&n
,&m
);
c
[0][0]=1;
fo(i
,1,n
+20){
c
[i
][0]=1;
fo(j
,1,20) c
[i
][j
]=(c
[i
-1][j
]+c
[i
-1][j
-1])%mo
;
}
while(m
--){
int l
,r
,k
;
scanf("%d %d %d",&l
,&r
,&k
);
b
[l
][k
]++;
fo(i
,0,k
) b
[r
+1][k
-i
]=(b
[r
+1][k
-i
]-c
[r
-l
+i
][i
]+mo
)%mo
;
}
fd(j
,20,0)
fo(i
,1,n
) b
[i
][j
]=(b
[i
][j
]+b
[i
-1][j
]+b
[i
][j
+1])%mo
;
fo(i
,1,n
) printf("%lld\n",b
[i
][0]);
}
