[AGC054B] Greedy Division

gaokj · 2023-08-25 10:29:58 · 题解

前言

这是某个同学让我给他讲的题目，结果他过来竟是为了看旁边一位同学玩游戏，然后我们过了这道题之后发现那位玩游戏的同学早就通过一些特殊方法过了这道题。

话说那个水太阳的题解是不是写复杂了一点。

思路

一眼 Dp，我们定义 f_{i,j,k} 前 i 个数选出 j 个和为 k 的方案数，这里因为我们前 i 个数一定要选所以知道了 B 选出的和。

那么我们的状态转移方程就位 f_{i,j,k}=f_{i-1,j,k}+f_{i-1,j-1,k-a_i} 这里就是分要它和不要它的这里我们分成两循环处理。

最后的答案就位 f_{n,i,sum\div2} 因为可以排列组合所以还要乘上 i 和 n-i 的阶乘。

代码

#include <bits/stdc++.h>
#define IOS std::ios::sync_with_stdio(fasle);cin.tie(NULL);cout.tie(NULL)
#define int long long
#define ri register int
#define rep(i,x,y) for(ri i=x;i<=y;i++)
#define rep1(i,x,y) for(ri i=x;i>=y;i--)
#define il inline
#define fire signed
#define pai(a,x,y) sort(a+x,a+y+1)
using namespace std ;
il int qmi(int a,int b) {
    int res=1;
    while(b) {
        if(b&1) res=(res*a);
        a=a*a;
        b>>=1;
    }
    return res;
}
void read(int &x) {
    x=false;
    ri f=1;
    char c=getchar();
    while(c>'9'||c<'0') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c-'0'<=9&&c>='0') {
        x=x*10+c-'0';
        c=getchar();
    }
    x*=f;
}
void print(int x) {
    if(x>=10) print(x/10);
    putchar(x%10+'0');
}
#define gcd(x,y) __gcd(x,y)
#define lcm(x,y) x*y/gcd(x,y)
const int N=110,mod=998244353;
int f[N][N][N*N];
int n,a[N],s;
int sbzhuang[N];
void init() {
    sbzhuang[0]=1;
    rep(i,1,n) sbzhuang[i]=sbzhuang[i-1]*i%mod;
}
fire main() {
    cin>>n;
    init();
    rep(i,1,n) cin>>a[i],s+=a[i];
    if(s&1) {
        return cout<<0<<endl,0;
    }
    f[0][0][0]=1;
    rep(i,1,n) {
        rep(j,0,i) {
            rep(k,a[i],s) {
                if(j>=1) (f[i][j][k]+=f[i-1][j-1][k-a[i]])%=mod;
            }
            rep(k,0,s) f[i][j][k]=(f[i][j][k]+f[i-1][j][k])%mod;
        }
    }
    int res=0;
    rep(i,1,n) (res+=(f[n][i][s/2])*sbzhuang[i]%mod*sbzhuang[n-i]%mod)%=mod;
    cout<<res;
    return false;
}