宝宝龙好强，拜谢宝宝龙
ridewindHE
·
·
题解
同机房大佬宝宝龙出的题，上午模拟赛被宝宝龙大佬拉爆了，写个题解膜拜一下他。
题意
## 思路
如果维护 $n$ 个数组时间复杂度是 $O(n^2 (p+q))$，显然会超时。
所以我们考虑维护 $a_{0}$，查询时求出 $a_{x,j}$ 包含多少个 $a_{0}$ 项，展开前缀和得：
$$
a_{x,j}=\sum_{i=1}^{j} a_{0,i}\times C_{j-i+x-1}^{x-1}
$$
那么：
$$
\sum_{j=l}^{r} a_{x,j}=\sum_{i=1}^{r}a_{0,i} \sum_{d=\max(l-i,0)}^{r-i}C_{d+x-1}^{x-1}
$$
然后利用插板法可得：
$$
\sum_{d=0}^{m}C_{d+x-1}^{x-1}=C_{m+x}^{x}
$$
所以内层求和可以 $O(1)$ 计算：
$$
\sum_{d=\max(l-i,0)}^{r-i}C_{d+x-1}^{x-1}=C_{x+r-i,x}-C_{x+\max(l-i,0)-1,x}
$$
因此查询操作已经解决，接下来，我们考虑区间加操作。
我们需要考虑 $a_{0}$ 要怎么改，才能让 $a_{x}$ 的 $[l,r]$ 项每项都加上 $k$。
首先 $a_{i}$ 是 $a_{i-1}$ 的前缀和数组，那么 $a_{i-1}$ 就是 $a_{i}$ 的差分数组。所以我们可以从 $a_{x}$ 出发，一层一层向下差分。
假设 $a_{x}$ 的 $[l,r]$ 项都加上了 $k$，那么 $a_{x-1}$ 的 $l$ 处 $+k$，$r+1$ 处 $-k$。
然后再从 $a_{x-1}$ 推到 $a_{x-2}$，那么 $a_{x-2}$ 的 $l$ 处 $+k$，$l+1$ 处 $-k$，$r+1$ 处 $-k$，$r+2$ 处 $+k$。
接着再从 $a_{x-2}$ 推到 $a_{x-3}$，那么 $a_{x-3}$ 的 $l$ 处 $+k$，$l+1$ 处 $-2\times k$，$l+2$ 处 $+k$，$r+1$ 处 $-k$，$r+2$ 处 $+2\times k$，$r+3$ 处 $-k$。
以此类推。
经过几次推导，我们可以得出结论，这个修改的数的符号由差分展开时的偏移量 $i$ 的奇偶性决定，系数很像一个杨辉三角，直接用组合数求即可。
时间复杂度 $O(n(p+q))$。
注意，修改时 $x=0$ 需要单独处理，$a_{0,i}$ 和 $k$ 可能为负数，要注意。
## 代码
:::success[AC code]
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int p=1e9+7;
ll qp(ll a,ll b){
a%=p;
ll res=1;
while(b){
if(b&1)res=res*a%p;
a=a*a%p,b>>=1;
}
return res;
}
ll fac[610],inv[610];
void init(int n){
fac[0]=inv[0]=1;
for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%p;
inv[n]=qp(fac[n],p-2);
for(int i=n-1;i>=1;i--)inv[i]=inv[i+1]*(i+1)%p;
}
ll C(int x,int y){
if(y>x||y<0)return 0;
return fac[x]*inv[x-y]%p*inv[y]%p;
}
int a[310];
int main(){
int n,q1,q2;
cin>>n>>q1>>q2;
int q=q1+q2;
init(n*2);
for(int i=1;i<=n;i++){
cin>>a[i];
a[i]=(a[i]%p+p)%p;
}
while(q--){
int op,x,l,r,k;
cin>>op>>x>>l>>r;
if(op==1){
cin>>k;
k=(k%p+p)%p;
if(!x){
for(int i=l;i<=r;i++)a[i]=(a[i]+k)%p;
continue;
}
for(int i=0;i<x&&l+i<=n;i++){
if(i&1)a[l+i]=((a[l+i]-k*C(x-1,i)%p)%p+p)%p;
else a[l+i]=(a[l+i]+k*C(x-1,i)%p)%p;
}
for(int i=0;i<x&&r+1+i<=n;i++){
if(i&1)a[r+1+i]=(a[r+1+i]+k*C(x-1,i)%p)%p;
else a[r+1+i]=((a[r+1+i]-k*C(x-1,i)%p)%p+p)%p;
}
}else{
int ans=0;
for(int i=1;i<=r;i++)ans=(ans+a[i]*((C(x+r-i,x)-C(x+max(l-i,0)-1,x))%p+p)%p)%p;
cout<<ans<<"\n";
}
}
return 0;
}
```
:::