[AGC054B] Greedy Division 的题解

Whispering_H · 2023-12-19 16:42:50 · 题解

题目大意

略。

大体思路

这题的一个重要结论就是：每一个排列 p 和操作都是一一对应的，这就是所谓的 双射关系。

发现了这个结论这题就解决了一大半了。

剩下的就是典型的背包+滚动数组了，dp 的具体过程可以看代码里的注释。

代码如下：

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int, int> pr;
const int mod = 998244353;

inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); }
    while(ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
    return x * f;
}

int _,n,a[107],sum,ans;
int dp[107][5007];
int fac[107];
//dp[i][j][k] 表示到了第 i 个数，选了 j 个数，和为 k 的方案数
//发现 dp[i][j][k] 只和 dp[i-1][j][k] 有关系，于是滚动第一维
//dp[j][k] 表示选了 j 个数，和为 k 的方案数
//我们需要求的是，和为 sum/2 的方案数
//答案就是 dp[j][sum/2]*(j!)*((n-j)!)(1<=j<=n) 的和
//乘上 (j!)*((n-j)!) 是因为我们的 dp 数组是不记录选取数字的顺序的
//我们需要把这种选取方案的所有情况全都加上
//这个可以预处理

inline void init(){
    fac[0]=1;
    for(int i=1;i<=100;i++)
        fac[i]=fac[i-1]*i%mod;
}

signed main(){
    init();
    n=read();
    for(int i=1;i<=n;i++) a[i]=read(),sum+=a[i];
    if(sum&1){ printf("0\n"); return 0; }
    //和是奇数，说明无法平均分成 2 份
    dp[0][0]=1;
    for(int i=1;i<=n;i++) //枚举到了第 i 个数
        for(int j=n;j>=1;j--) //选了 j 个数 由于滚动数组，j 要倒序枚举
            for(int k=sum/2;k>=a[i];k--) //和为 k
                dp[j][k]=(dp[j][k]+dp[j-1][k-a[i]])%mod; //方案数要累加

    for(int i=1;i<=n;i++)
        ans=(ans+fac[i]*fac[n-i]%mod*dp[i][sum/2]%mod)%mod;
    printf("%lld\n",ans);
    return 0;
}