题解 P8367【[LNOI2022] 盒】
whiteqwq
·
·
题解
P8367 [LNOI2022] 盒 解题报告：
更好的阅读体验
还是不够熟练啊。。。
题意
数轴上有 n 个位置有球，第 i 个位置有 a_i 个，将一个球从 i 移动到 i+1（或从 i+1 移动到 i）需要花费 w_i 的代价。
你可以进行任意次操作，对于所有的结果数量序列 b，计数 a 变成 b 的最小代价之和。
## 分析
列出 dp（或直接考虑贡献），化为式子可得：
$$
\sum_{i=1}^{n-1}w_i\sum_{j=0}^S|j-sum_i|{j+i-1\choose i-1}{n-i-1+S-j\choose n-i-1}
$$
上面相当于对后面的式子线性组合，我们考虑要对于每个 $i$ 计算：（$C=sum_i,S$）
$$
\sum_{j=0}^C{j+i-1\choose i-1}{n-i-1+S-j\choose n-i-1}
$$
$$
\sum_{j=0}^Cj{j+i-1\choose i-1}{n-i-1+S-j\choose n-i-1}
$$
$$
=i\sum_{j=0}^{C-1}{j+i\choose i}{n-i-2+S-j\choose n-i-1}
$$
先尝试 $C=S-c$：
$$
\sum_{j=0}^{S-c}{j+i+c-1\choose i+c-1}{n-i-1+S-c-j\choose n-i-1}={n+S-1\choose n+c-1}
$$
范德蒙德卷积本质上是格路计数，我们想类似格路计数地处理：
$$
\sum_{j=0}^A{B+j\choose B}{C-B-1+D-j\choose C-B-1}
$$
考察其组合意义，即为 $(0,0)$ 走到 $(C,D)$，在从第 $B$ 列走到 $B+1$ 列时，其对应行不超过 $A$。
类似类欧几里得算法，我们将坐标系翻转，问题变成了从 $(0,0)$ 走到 $(D,C)$，在从 $A$ 列走到 $A+1$ 列时，其对应行超过了 $B$，于是上式又可写作：
$$
\sum_{j=B+1}^C{A+j\choose A}{D-A-1+C-j\choose D-A-1}
$$
由于 $sum_i$ 递增，我们只需用两个指针模拟 $A$ 和 $B$ 的增加，$A$ 移动时变化上面的式子，$B$ 移动时变化下面的式子即可，复杂度线性。
## 代码
组合数之和可以写一个结构体一起维护，这样比较方便。
```cpp
#include<stdio.h>
#include<stdlib.h>
char buf[1<<21],*p1=buf,*p2=buf,obuf[1<<21],*O=obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
const int maxn=500005,maxN=2500005,mod=998244353;
int T,n,S,res;
int a[maxn],sum[maxn],fac[maxN],nfac[maxN];
int ksm(int a,int b){
int res=1;
while(b){
if(b&1)
res=1ll*res*a%mod;
a=1ll*a*a%mod,b>>=1;
}
return res;
}
void read(int &x){
x=0;
char c=getchar();
for(;c<'0'||c>'9';c=getchar());
for(;c>='0'&&c<='9';c=getchar())
x=x*10+c-48;
}
inline int C(int a,int b){
return a<b? 0:1ll*fac[a]*nfac[b]%mod*nfac[a-b]%mod;
}
struct binom{
int a,b,c,d,s;
void init(int cc,int dd){
a=b=0,c=cc,d=dd,s=C(c+d-1,c-1);
}
int calc(int aa,int bb){
while(a<aa)
a++,s=(s+1ll*C(b+a,a)*C(c-b-1+d-a,c-b-1))%mod;
while(b<bb)
b++,s=(s+1ll*(mod-C(a+b,a))*C(d-a-1+c-b,d-a-1))%mod;
return s;
}
}B1,B2;
int main(){
fac[0]=1;
for(int i=1;i<maxN;i++)
fac[i]=1ll*fac[i-1]*i%mod;
nfac[maxN-1]=ksm(fac[maxN-1],mod-2);
for(int i=maxN-1;i>=1;i--)
nfac[i-1]=1ll*nfac[i]*i%mod;
read(T);
while(T--){
read(n),res=0;
for(int i=1;i<=n;i++)
read(a[i]),sum[i]=sum[i-1]+a[i];
S=sum[n],B1.init(n-1,S),B2.init(n,S-1);
for(int i=1,x;i<n;i++){
int ans=0;
ans=(1ll*i*C(n+S-1,n)+1ll*(mod-sum[i])*C(n+S-1,n-1))%mod;
if(sum[i]){
ans=(ans+2ll*sum[i]*B1.calc(sum[i],i-1))%mod;
ans=(ans+2ll*(mod-i)*B2.calc(sum[i]-1,i))%mod;
}
read(x),res=(res+1ll*ans*x)%mod;
}
printf("%d\n",res);
}
return 0;
}
```