P8863 题解
Special_Judge
·
·
题解
P8863 「KDOI-03」构造数组 题解
做完看了一下题解发现一眼看过去都好复杂
讲一下自己推出来的做法。
首先可以明确，\sum b_i \equiv 1 \pmod 2 的时候，一定无解，因为每次操作都会使整个数列的和增加 2，而 a_i 初始均为 0，所以数列的和始终为偶数，不可能出现 \sum b_i \equiv 1 \pmod 2 的情况。
那么我们我们不妨来转换一下问题，设 m=\dfrac{\sum b_i}{2}，那么题意就变为了：给定 m 个括号，每一个括号都形如 (\quad ,\quad)，即需要往里面填 2 个数，填的数在 [1,n] 之间，同一括号内的数不相同，并且 i 在 m 个括号中出现 b_i 次。
来手玩一下样例 1。首先只考虑填 1 的话我们的方案就有 C_{4}^{2} 种。
那么接下来我们要填 2。如果我们只考虑填 1 和 2 的话我们的方案数就有 C_{4}^2 \cdot C_{4}^2 种。但是我们注意到我们填 2 的位置是会改变填 3 的方案数的。因为如果填进了已经填过 1 的位置，这个括号就填满了，3 的可选位置就变少了。
此时注意到数据范围 1 \le n \le 5000,\sum b_i \le 30000，可以猜想这道题目可能是 DP。结合上面的思考，我们就应该设计 DP 状态为 f_{i,j}，第一维 i 表示填完了前 i 个数，第二维 j 表示有 j 个括号已经被填满。
下面设 s_i=\sum \limits _{k=1}^i b_k。
状态转移时，我们不妨考虑填完前 i-1 个数已经被填满的括号数 k \in [0,j]，那么为了让填完的括号数变为 j，我们需要从 s_{i-1}-2k 个填了 1 个数的括号中选择 j-k 个括号填上 i，同时从 m-k-(s_{i-1}-2k)=m+k-s_{i-1} 个空括号中选择 b_i-(j-k) 个填上剩下的 i。所以状态转移方程为：
f_{i,j}=\sum_{k \in [0,j]} f_{i-1,k} \cdot C_{s_{i-1}-2k}^{j-k} \cdot C_{m+k-s_{i-1}}^{b_i-(j-k)}
另外我们注意到，最好控制一下使得这些组合中的数不为负。这样我们可以进一步缩小 k 的取值范围，只有这样时间复杂度才是对的。
综上所述，设：
$$
l=\max \{ 0,j-b_i,s_{i-1}-m \} \\
r=\min \{ j,\frac{s_{i-1}}{2} \}
$$
状态转移方程变为：
$$
f_{i,j}=\sum_{k \in [l,r]} f_{i-1,k} \cdot C_{s_{i-1}-2k}^{j-k} \cdot C_{m+k-s_{i-1}}^{b_i-(j-k)}
$$
其中初始状态为 $f_{0,0}=1$，最终答案即为 $f_{n,m}$。
注意到 $n \cdot m$ 非常大，要开这么大的 $f$ 数组是不可能的。又注意到 $f_i$ 的转移只和 $f_{i-1}$ 有关，因此用滚动数组优化。
注意到 $j-(j-b_i)=b_i$，所以枚举 $k$ 的循环次数不会太多。时间复杂度大概是 $O(m^2)$，4s 时限下稳过。
代码：
```cpp
#include<bits/stdc++.h>
#define int long long
#define here(x) {cout<<"here "<<x<<endl;}
#define putlist(x,st,ed) {for(int ind=st;ind<=ed;ind++)cout<<x[ind]<<' ';cout<<endl;}
#define putstl(x) {for(auto TeMp:x)cout<<TeMp<<' ';cout<<endl;}
#define putsize(x) cout<<sizeof(x)*1.0/1024/1024<<" MB"<<endl;
#define cases int __;cin>>__;while(__--)work();
#define MAXN_INT 2147483647
#define MAXN_LL 9223372036854775807ll
#define N 5010
#define M 30010
#define eps 1e-6
#define mp make_pair
#define pb push_back
using namespace std;
const int MOD=998244353;
namespace Combination {
int qpow(int x,int y) {
int res=1;
while(y) {
if(y&1)res=res*x%MOD;
x=x*x%MOD;
y>>=1;
}
return res;
}
int fac[M],inv[M];
void setup(int lim) {
fac[0]=1;
for(int i=1;i<=lim;i++) {
fac[i]=fac[i-1]*i%MOD;
}
inv[lim]=qpow(fac[lim],MOD-2);
for(int i=lim-1;i>=1;i--) {
inv[i]=inv[i+1]*(i+1)%MOD;
}
}
int comb(int n,int m) {
if(n<m)return 0;
else if(n==m||m==0)return 1;
else if(n==0)return 0;
else return fac[n]*inv[m]%MOD*inv[n-m]%MOD;
}
}
using namespace Combination;
int n,m;
int b[N],s[N];
int ol=0,ne=1;
int f[2][M];
signed main() {
cin>>n;
for(int i=1;i<=n;i++) {
cin>>b[i];
s[i]=s[i-1]+b[i];
}
m=s[n]/2;
f[ol][0]=1;
setup(M-5);
for(int i=1;i<=n;i++) {
for(int j=0;j<=m;j++) {
int l=max({0ll,j-b[i],s[i-1]-m});
int r=min(j,s[i-1]/2);
f[ne][j]=0;
for(int k=l;k<=r;k++) {
f[ne][j]=(f[ne][j]+f[ol][k]*comb(s[i-1]-2*k,j-k)%MOD*comb(m+k-s[i-1],b[i]-j+k)%MOD)%MOD;
}
}
swap(ol,ne);
}
cout<<f[ol][m]<<endl;
return 0;
}
/*
*/
```