AT_xmascon20_f 题解
dAniel_lele
·
·
题解
首先 exchange argument 一下可以知道确定扔掉哪些的时候，一定会按 $b_i$ 单调递减的顺序去做菜。
考虑如何对于给定的 $a_i$ 计算答案（$b_i$ 排序好了）。先二分，然后从前往后扫，将 $a_i$ 扔进一个 pq 里面。如果目前的前缀和加上 $b_i$ 比二分的值大了，那就弹出 pq 中最大的并不选他。容易理解这么做的正确性。
考虑经典 trick dp 维护 pq。枚举二分的值，设计 $dp_{i,j,k,l,0/1/2}$ 表示看到 $i$，考虑所有我们打算不选的东西之后目前前缀和为 $j$，不选了 $k$ 个，目前选不选的分界线为 $l$。$0/1/2$ 为辅助维度，分别表示目前没有见到任何 $l$，见到了 $l$ 且全选了，见到了 $l$ 选了且有一段后缀没选。
注意这里我们不需要记录 pq 里面剩了多少数，因为是否弹出只跟是否会爆有关，就不用在 pq 清空的时候将 $l$ 变大了，每次判断 $j+b_i+l$ 如果大于二分的值，那么相当于顶满了，就可以将 $l$ 转移到更大的位置。注意最后一维 $1$ 可以转移到 $\geq l$ 而 $2$ 可以转移到 $>l$。
一个小问题是对于不删的位置，我们还需要保证 $j+b_i$ 小于等于二分的值，在这类转移的时候判一下即可。
这么做复杂度是 $O(n^4v^3)$ 的，感觉已经能过了。
考虑优化，注意到我们只在乎（二分的值不妨设为 $lim$）$lim-j$ 的值，让 $nv+\max b_i$ 次 dp 并行即可，总复杂度 $O(n^3v^2)$。
统计答案是容易的，不再阐述。
```
#include <bits/stdc++.h>
#define mid ((l+r)>>1)
#define lowbit(i) (i&(-i))
using namespace std;
const int mod=998244353;
int qp(int a,int b){
int ans=1;
while(b){
if(b&1) ans=1ll*ans*a%mod;
a=1ll*a*a%mod;
b>>=1;
}
return ans;
}
inline void add(int &i,int j){
i+=j;
if(i>=mod) i-=mod;
}
inline int addv(int i,int j){
i+=j;
if(i>=mod) i-=mod;
return i;
}
int b[35];
int dp[31][1205][31][22][3];
int tmp[1205][31][22][3];
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int n,v; cin>>n>>v;
for(int i=1;i<=n;i++) cin>>b[i];
sort(b+1,b+n+1); reverse(b+1,b+n+1);
for(int t=0;t<=1200;t++) for(int j=1;j<=v+1;j++) dp[0][t][0][j][0]=1;
for(int i=1;i<=n;i++){
memset(tmp,0,sizeof(tmp));
for(int j=0;j<=1200;j++){
for(int k=0;k<i;k++){
for(int l=1;l<=v+1;l++){
if(!dp[i-1][j][k][l][0]&&!dp[i-1][j][k][l][1]&&!dp[i-1][j][k][l][2]) continue;
{
//choose <l
add(tmp[max(0,j-l+1)][k][l][0],dp[i-1][j][k][l][0]);
add(tmp[max(0,j-l+1)][k][l][1],dp[i-1][j][k][l][1]);
add(tmp[max(0,j-l+1)][k][l][2],dp[i-1][j][k][l][2]);
add(tmp[j][k][l][0],mod-dp[i-1][j][k][l][0]);
add(tmp[j][k][l][1],mod-dp[i-1][j][k][l][1]);
add(tmp[j][k][l][2],mod-dp[i-1][j][k][l][2]);
}
if(l!=v+1){
//choose =l
add(dp[i][j][k+1][l][1],dp[i-1][j][k][l][0]);
add(dp[i][j][k+1][l][1],dp[i-1][j][k][l][1]);
if(j-l>=0&&j-l>=b[i]){
add(dp[i][j-l][k][l][2],dp[i-1][j][k][l][1]);
add(dp[i][j-l][k][l][2],dp[i-1][j][k][l][2]);
}
}
if(l!=v+1){
//choose >l
add(dp[i][j][k+1][l][0],1ll*dp[i-1][j][k][l][0]*(v-l)%mod);
add(dp[i][j][k+1][l][1],1ll*dp[i-1][j][k][l][1]*(v-l)%mod);
add(dp[i][j][k+1][l][2],1ll*dp[i-1][j][k][l][2]*(v-l)%mod);
}
}
}
}
for(int j=0;j<=1200;j++){
for(int k=0;k<i;k++){
for(int l=1;l<=v+1;l++){
if(j){
add(tmp[j][k][l][0],tmp[j-1][k][l][0]);
add(tmp[j][k][l][1],tmp[j-1][k][l][1]);
add(tmp[j][k][l][2],tmp[j-1][k][l][2]);
}
if(j>=b[i]){
add(dp[i][j][k][l][0],tmp[j][k][l][0]);
add(dp[i][j][k][l][1],tmp[j][k][l][1]);
add(dp[i][j][k][l][2],tmp[j][k][l][2]);
}
}
}
}
memset(tmp,0,sizeof(tmp));
for(int j=0;j<=1200;j++){
for(int k=0;k<=i;k++){
for(int l=1;l<=v+1;l++){
if(b[i]+l>j){
add(tmp[j][k][l][0],dp[i][j][k][l][1]);
add(tmp[j][k][l+1][0],dp[i][j][k][l][2]);
dp[i][j][k][l][1]=0;
dp[i][j][k][l][2]=0;
}
}
}
}
for(int j=0;j<=1200;j++){
for(int k=0;k<=i;k++){
for(int l=1;l<=v+1;l++){
add(tmp[j][k][l][0],tmp[j][k][l-1][0]);
add(dp[i][j][k][l][0],tmp[j][k][l][0]);
}
}
}
}
for(int i=1;i<=n;i++){
int j=n-i,ans=0;
for(int k=0;k<=1200;k++){
for(int nd=j+1;nd<=n;nd++){
add(ans,dp[n][k][nd][v+1][0]);
}
}
cout<<ans<<" \n"[i==n];
}
return 0;
}
```