SCP-J 2026 T4
gitxiaozheng
·
·
题解
Solution
看到这一题一开始以为是数据结构题，然而其实是数学题。
不妨对 A_0 求其差分数组 D，然后由于显然 A_k 为差分数组 D 的 k+1 阶前缀和，能得到：
A_{k,j}=\sum^{j}_{i=1}D_i\binom{j-i+k}{k}
反过来，D 数组就是 A_k 数组的 k+1 阶差分：
D_i=\sum^{k+1}_{j=0}(-1)^{j}\binom{k+1}{j}A_{k,i-j}
对于操作 1 中对 A_x 的修改，我们可以引入一个数列 d，表示 A_x 数组的增量数组的一阶差分。很容易得出只有 d_l=k 和 d_{r+1}=-k，其他项都是 0。把它做 x 阶差分，得到数列 d'：
d'_i=\sum^{x}_{j=0}(-1)^{j}\binom{x}{j}d_{i-j}
因为 d 中很多项都是 0，最后我们化简会得到（下面 i 是介于 0 和 x 之间的整数）：
d'_{l+i}=k\binom{x}{i}(-1)^i
d'_{r+i+1}=-k\binom{x}{i}(-1)^i
当然 d' 除了上述项，其他项都是 0。
只需拿 d' 去更新 D，就完成了操作 1。
对于操作 2 就简单了。利用组合恒等式 \sum_{j=i}^{r}\binom{j-i+x}{x}=\binom{r-i+x+1}{x+1}，可以对所求式子进行一些转化：
\begin{aligned}
&\sum^{r}_{j=l}A_{x,j}\\
&=\sum^{r}_{j=l}\sum^{j}_{i=1}D_i\binom{j-i+x}{x}\\
&=\sum^{r}_{i=1}D_i\sum^{r}_{j=\max(i,l)} \binom{j-i+x}{x}\\
&=\sum^{r}_{i=1}D_i\left( \sum_{j=i}^r \binom{j-i+x}{x}
-\sum_{j=i}^{l-1}\binom{j-i+x}{x} \right)\\
&=\sum_{i=1}^{r}D_i\left[\binom{r-i+x+1}{x+1}-\binom{l-1-i+x+1}{x+1}\right]\\
\end{aligned}
这样就化成了可做的形式。
:::success[AC code & 提交记录]
代码由赛后整理。
```cpp
//edit by devc++
//by gitxiaozheng/dakada
//我还以为是ds
#include<bits/stdc++.h>
using namespace std;
#define L long long
#define iotype L //zigai
#define space putchar(' ')
#define enter putchar('\n')
inline iotype qcin();
void qcout(iotype);
const L mod=1e9+7,maxn=310,maxpq=1e5+10;
int tot=0;
L Jc[maxn*2],Jcinv[maxn*2];
int diff[maxn];
int a[maxn];
L qpow(L a,L b){
L res=1,base=a;
while(b){
if(b&1){
res=(base*res)%mod;
}
base=(base*base)%mod;
b>>=1;
}
return res;
}
void predone(int n){
Jc[0]=1;
for(L i=1;i<=n;i++){
Jc[i]=(Jc[i-1]*i)%mod;
}
Jcinv[n]=qpow(Jc[n],mod-2);
for(L i=n-1;i>=0;i--){
Jcinv[i]=(Jcinv[i+1]*(i+1))%mod;
}
}
L C(L n,L m){
if(m<0||m>n||n<0)return 0;
return ((Jc[n]*Jcinv[m])%mod*Jcinv[n-m])%mod;
}
void add(int x,int l,int r,L k,int n){
for(int i=0;i<=x;i++){
L val=((k*C(x,i))%mod*(i&1?-1:1)+mod)%mod;
int a1=l+i,b1=r+i+1;
if(a1<=n){
diff[a1]=((diff[a1]+val)+mod)%mod;
}
if(b1<=n){
diff[b1]=((diff[b1]-val)+mod)%mod;
}
}
}
L query(int x,int l,int r,int n){
L res=0;
for(int i=1;i<=r;i++){
if(!diffs[i])continue;
res=(res+(1ll*diff[i]*(C(r-i+x+1,x+1)-C(l-1-i+x+1,x+1)+mod)%mod)%mod)%mod;
}
return res;
}
signed main(){
//Your code is here...
int n=qcin(),p=qcin(),q=qcin();
predone(n*2+10);
for(int i=1;i<=n;i++){
a[i]=(qcin()+mod)%mod;
diff[i]=(a[i]-a[i-1]+mod)%mod;
}
for(int Q=p+q;Q;Q--){
int op=qcin(),x=qcin(),l=qcin(),r=qcin();
if(op==1){
L k=(qcin()+mod)%mod;
add(x,l,r,k,n);
}else{
qcout(query(x,l,r,n));
enter;
}
}
return 0;
}
inline iotype qcin(){
iotype k=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-'){
f=-1;
}
c=getchar();
}
while(c>='0'&&c<='9'){
k=k*10+c-'0';
c=getchar();
}
return k*f;
}
void qcout(iotype x){
static int num[20];
int tot=0;
if(x<0){
putchar('-');
x=-x;
}
while(x>=10){
num[++tot]=x%10;
x/=10;
}
putchar(x+'0');
for(int i=tot;i>=1;i--){
putchar(num[i]+'0');
}
}
```
[提交记录](https://www.luogu.com.cn/record/303930616)。
:::