P8863 「KDOI-03」构造数组 题解

· · 题解

模拟赛 T4。赛时认为这是不可做题，遂打爆搜拿 60pts 跑路。结果午睡之后再看很快就瞪出来做法了。所以是因为上午没有午睡导致脑子不清醒。

观察题目中的操作，每次选两个不同的下标进行 +1 操作。也就是说一共 \sum b_i/2 个操作，每个操作都有两个不相等的参数。i 会在操作中出现 b_i 次。我们从小到大填参数。对于每个状态，我们只关心有多少个操作只填了一个参数。

约定：s_i 表示 \sum_{j=1}^ib_i。

设 f_{i,j} 表示考虑完前 i 个下标，有 j 个操作只确定了较小的一个参数，其余的参数所在的操作都已经确定了两个参数。转移的时候，枚举有 k 个参数用来补全只填了一个参数的操作。得到如下转移：

f_{i,j-k+b_i-k}\leftarrow \dbinom{j}{k}\dbinom{s_N/2-((s_{i-1}-j)/2+j)}{b_i-k}f_{i-1,j}

直接枚举转移即可。时间复杂度 O((\sum b_i)^2)。

#include<bits/stdc++.h> 
#define ll long long
using namespace std;
void rd(){}
template<typename T,typename... U> void rd(T &x,U&... arg){
    x=0;int f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();
    x*=f;rd(arg...);
}
const int maxn=5005,maxv=30005,P=998244353;
int N,a[maxn],s[maxn];
ll f[2][maxv>>1],fac[maxv],inv[maxv];
inline ll C(int n,int m){
    if(n<m||m<0) return 0;
    return fac[n]*inv[m]%P*inv[n-m]%P;
}
int main(){
    rd(N);
    for(int i=1;i<=N;i++) rd(a[i]),s[i]=s[i-1]+a[i];
    fac[0]=fac[1]=inv[0]=inv[1]=1;
    for(int i=2;i<=s[N];i++)
        fac[i]=fac[i-1]*i%P,
        inv[i]=(P-P/i)*inv[P%i]%P;
    for(int i=2;i<=s[N];i++) (inv[i]*=inv[i-1])%=P;
    f[0][0]=1;
    for(int i=1,t=1;i<=N;i++,t^=1){
        memset(f[t],0,sizeof f[t]);
        for(int j=0;j<=min(s[i-1],s[N]-s[i-1]);j++)
            for(int k=0;k<=min(j,a[i]);k++){
                if(j-k+a[i]-k>s[N]-s[i]) continue;
                (f[t][j-k+a[i]-k]+=C(j,k)*
                C(s[N]/2-(s[i-1]+j)/2,a[i]-k)%P*f[!t][j])%=P;
            }
    }
    printf("%lld",f[N&1][0]);
    return 0;
}