1.部分分1(k=1)
随便乱搞,没啥说的,代码也不想放
if(k==1){
ll x;
for(register int i=1,opt;i<=m;i++){
opt=read();
if(opt==0){
x=lread();
n++;sum+=x;
if(sum>=mol)sum-=mol;
}else{
sum+=n;
if(sum>=mol)sum-=mol;
}
printf("%lld\n",sum);
}
}
2.部分分2(k=2,k=3)
如果你做过osu那道期望DP的题,发现k=2,3的情况都很简单
全局加一可以直接维护一个\(x\)的和
\((x+1)^2-x^2=2\times x+1\)
插数直接加就行,
k=3类似
if(k==2){
ll x;
for(register int i=1,opt;i<=m;i++){
opt=read();
if(opt==1){
sum=((sum+2*sum1%mol)%mol+n)%mol,sum1+=n;
if(sum1>=mol)sum1-=mol;
}else{
n++;x=lread();
sum1+=x;
sum+=1LL*x*x%mol;
if(sum1>=mol)sum1-=mol;
if(sum>=mol)sum-=mol;
}
printf("%lld\n",sum);
}
}else if(k==3){
ll x;
for(register int i=1,opt;i<=m;i++){
opt=read();
if(opt==1){
sum=(((sum+3*sum1%mol)%mol+3*sum2%mol)%mol+n)%mol,sum1=((sum1+2*sum2%mol)%mol+n)%mol,sum2+=n;
if(sum2>=mol)sum2-=mol;
}else{
n++;x=lread();
sum2+=x;
sum1+=1LL*x*x%mol;
sum+=1LL*x*x*x%mol;
if(sum2>=mol)sum2-=mol;
if(sum1>=mol)sum1-=mol;
if(sum>=mol)sum-=mol;
}
printf("%lld\n",sum);
}
}
3.部分分3(\(m<=2e5,k<=50\))
运用部分分二的思想,又观察到\(k\)很小,所以可以直接开一个\(50\)的桶
现在思考,\(x^k\)如何由\(x^{k-1},x^{k-2},x^{...}\)转移过来
发现就是组合数的转移,那么直接杨辉三角预处理组合数,一边转移一边从大到小更新答案
时间总和:\(200000\times 50=10000000\)
照例说应该能稳过,但是各种乘法和取模让常数变得巨大
因此应该用一些玄学的卡常技巧
观察到模数是\(1e9+7\),相乘不会超\(ull\),所以乘法直接模,加法加到十几次在模
for(register int i=1;i<=m;++i){
opt=read();
int dclock=0;
if(opt==1){
for(register int j=1;j<=k;++j){
dclock++;
sum+=summ[k-j]*c[k][j]%mol;
if(dclock==17)sum%=mol,dclock=0;
}
for(register int j=k;j>=0;--j){
for(register int p=j;p>=1;--p){
cclock[j]++;
summ[j]+=c[j][p]*summ[j-p]%mol;
if(cclock[j]==17)summ[j]%=mol,cclock[j]=0;
}
}
}else{
n++;x=read();
now=1;
for(register int j=1;j<=k;++j){
cclock[j-1]++;
summ[j-1]+=now;
if(cclock[j-1]==17)summ[j-1]%=mol,cclock[j-1]=0;
if(now*x>=mol)now=now*x%mol;
else now=now*x;
}
sum+=now;
if(sum>=mol)sum%=mol;
}
sum%=mol;
printf("%llu",sum);
putchar('\n');
}