P8863 「KDOI-03」构造数组
cplusoj：SS241113D. 构造数组 (array)
题意
给你一个长度为 \(n\le 5000\) 的数组 \(\{b\}\)，满足 \(\sum b \le 30000\)。每次操作你可以选择两个下标 \(i,j,i \neq j\)，将 \(b_i,b_j\) 减 \(1\)，问有多少种操作方式使得 \(b\) 变成全部是 \(0\)。
思路
看完题解之后发现并不是很难？？？（
设 \(s_i = \sum_{j=1}^i b_i\)，显然当 \(s_n\) 为奇数的时候答案为 \(0\)，因为每次操作都会使总和减 \(2\)。
刻画一下操作，相当于一共有 \(\frac{s_n}{2}\) 个桶，每个数字需要选择 \(b_i\) 个不相同的桶，每个桶只能装 \(2\) 个数字。
其中每个数字选择的桶的顺序是不重要的，因为无论你如何顺序选桶，最终我都会按照桶的编号顺序操作。
容易想到状压。
发现每个桶其实本质相同，都是只能装两个数字，因此我们不需要即每个桶的状态。只需要记 \(k_{0/1/2}\) 表示已经装了 \(0/1/2\) 个数字的桶有多少个。
因此可以设 \(f_{i,k_0,k_1,k_2}\) 表示处理到第 \(i\) 个数字，已经装了 \(0/1/2\) 个数字的桶有 \(k_{0/1/2}\) 个，的方案数。
转移的时候，枚举第 \(i\) 个数字往 \(0/1\) 的桶里分别装了多少个桶，往已经装了 \(1\) 个数字的桶里选了 \(j\) 个桶，那么 \(0\) 的桶就选了 \(b_i-j\) 个桶。转移方程就是
\[f_{i+1,k_0-b_i+j,k_1+b_i-j-j,k_2+j} \gets \binom{k_0}{b_i-j} \binom{k_1}{j} f_{i,k_0,k_1,k_2} \]比较显然的是我们不需要维护三个 \(k\)，实际上我们只需要维护 \(1\) 个 \(k\)。
设 \(k\) 表示已经装了 \(1\) 个球的的桶有多少个。
\[\begin{cases} k_0=\frac{s_n}{2}-k_1-k_2\\ k_1=k\\ k_2=\frac{s_{i-1}-k_1}{2} \end{cases} \]整理一下，转移式子就是
\[f_{i+1,k+b_i-2j} \gets \binom{\frac{s_n}{2}-k-\frac{s_{i-1}-k}{2}}{b_i-j} \binom{k}{j} f_{i,k} \]状态数是 \(O(n\sum b)\) 的，好像甚至不需要滚动数组，不过滚一下也无妨，把第一维滚掉。转移的时候枚举 \(k\) 是 \(O(\sum b)\) 的，枚举 \(j\) 是 \(O(b_i)\) 的，因此复杂度 $O((\sum b)^2)，可以算出来的有至少 \(\frac{1}{4}\) 的常数。
code
#include<bits/stdc++.h>
#define sf scanf
#define pf printf
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
typedef long long ll;
namespace poetry {
constexpr int N=5e3+7,mod=998244353,M=3e4+7;
int n,b[N],s[N];
int jc[M],inv[M];
int f[2][M];
int add(int a,int b) { return a+b>=mod ? a+b-mod : a+b; }
void _add(int &a,int b) { a=add(a,b); }
ll ksm(ll a,ll b=mod-2) {
ll s=1;
while(b) {
if(b&1) s=s*a%mod;
a=a*a%mod;
b>>=1;
}
return s;
}
void init() {
jc[0]=1;
rep(i,1,s[n]>>1) jc[i]=1ll*jc[i-1]*i%mod;
inv[s[n]>>1]=ksm(jc[s[n]>>1]);
per(i,(s[n]>>1)-1,0) inv[i]=1ll*inv[i+1]*(i+1)%mod;
}
ll c(int n,int m) {
if(m>n) return 0;
return 1ll*jc[n]*inv[m]%mod*inv[n-m]%mod;
}
void main() {
sf("%d",&n);
rep(i,1,n) sf("%d",&b[i]);
sort(b+1,b+n+1);
rep(i,1,n) s[i]=s[i-1]+b[i];
if((s[n]&1)||n==1) puts("0"), exit(0);
if(n==2) {
if(b[1]==b[2]) puts("1");
else puts("0");
exit(0);
}
init();
f[1][0]=1;
rep(i,1,n) {
int lim=i-2<0 ? 0 : s[i-2]+1;
memset(f[(i&1)^1],0,sizeof(int)*lim);
rep(k,0,s[i-1]) {
if(f[i&1][k])
rep(j,0,b[i]) {
if(k+b[i]-(j<<1)<0) break;
_add(f[(i&1)^1][k+b[i]-(j<<1)],c((s[n]>>1)-k-((s[i-1]-k)>>1),b[i]-j)*c(k,j)%mod*f[i&1][k]%mod);
}
}
}
pf("%d\n",f[(n+1)&1][0]);
}
}
int main() {
#ifdef LOCAL
freopen("my.out","w",stdout);
#else
freopen("array.in","r",stdin);
freopen("array.out","w",stdout);
#endif
poetry :: main();
}