「KDOI-03」构造数组 题解

· · 题解

测试点 1~3

输出不可以，总司令 0 即可。

测试点 4~5

输出 [b_1=b_2]。其实输出 1 即可，我没给 0 的点。

测试点 6~8

暴力，咋暴力都行，数据太小了。

测试点 9~11

这个可以用状压 dp，毕竟 b_i=1。

测试点 12~14

稍微转化一下，转化为：

有 n 个人要完成 \frac{n}{2} 份大作业，两个人一组完成大作业，需要按顺序提交作业，求方案数。

考虑对于每个人选搭档，第 1 个人有 n-1 种选择，第 2 个人 n-3 种，以此类推，最后乘 \frac{n}{2}! 即可。

测试点 15~18

状压 dp，考虑每次操作已经选个 0/1/2 个数组中的位置的方案数，可以压位存下来，转移只需要枚举数组这个位置要在哪些操作中被操作即可。复杂度还是要看实现，最快可以达到 O(3^{\frac{\sum b_i}{2}}\times n)，慢一点的也能过。

测试点 19~25

发现不同操作位置本质相同，首先考虑 dp_{i,j,k} 表示看到第 i 个数组位置，有 j 个操作位置目前为 1，k 个为 2。转移需要枚举往目前 0/1 个的位置分别转移多少个，复杂度 O((\sum b_i)^2(n+\sum b_i))，可以通过 19\sim 20 点。

容易发现只需要记录 2 操作个数，0/1 操作个数都可以通过某些方式计算，时间与空间复杂度变为 O((\sum b_i)(n+\sum b_i))，可以通过 21\sim 22 点。

然后分析一下，实际上操作位置只有 \frac{\sum b_i}{2} 个，同时空间可以滚动数组优化，最终复杂度为 O((\sum b_i)^2)，\frac{1}{4} 倍常数，实际循环次数约为 2.25\times 10^8，可以通过本题。

代码

#include <bits/stdc++.h>
using namespace std;
const int mod=998244353;
int qp(int a,int b){
    int ans=1;
    while(b){
        if(b&1) ans=((long long)ans*a)%mod;
        a=((long long)a*a)%mod;
        b>>=1;
    }
    return ans;
}
int fac[100005],inv[100005];
void init(){
    fac[0]=1;
    for(int i=1;i<=100000;i++) fac[i]=(long long)fac[i-1]*i%mod;
    inv[100000]=qp(fac[100000],mod-2);
    for(int i=99999;i>=0;i--) inv[i]=(long long)inv[i+1]*(i+1)%mod;
}
int C(int i,int j){
    if(i<0||j<0||i<j) return 0;
    return (long long)fac[i]*inv[i-j]%mod*inv[j]%mod;
}
int b[50005],n,pre[50005],dp[2][50005];
signed main(){
    init();
    cin>>n;
    for(int i=1;i<=n;i++) cin>>b[i],pre[i]=pre[i-1]+b[i];
    if(pre[n]%2==1) return cout<<0,0;
    int sum=pre[n]/2;
    dp[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=sum;j++){
            int tp2=j,tp1=pre[i-2]-j*2,tp0=sum-tp2-tp1;
            if(tp0<0) continue;
            dp[i&1][j]=0;
        }
        for(int j=0;j<=sum;j++){
            int tp2=j,tp1=pre[i-1]-j*2,tp0=sum-tp2-tp1;
            if(tp0<0) continue;
            for(int k=0;k<=b[i];k++){
                if(tp1<k||tp0<b[i]-k) continue;
                if(dp[(i&1)^1][tp2]) (dp[i&1][tp2+k]+=(long long)dp[(i&1)^1][tp2]*C(tp1,k)%mod*C(tp0,b[i]-k)%mod)%=mod;
            }
        }
    }
    cout<<dp[n&1][sum];
    return 0;
}