专栏文章

AT_xmascon20_f 题解

ddAniel_lele正虚像
AT_xmascon20_f题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@minzgcx4
此快照首次捕获于
2025/12/02 10:52
3 个月前
此快照最后确认于
2025/12/02 10:52
3 个月前
查看原文
O(n3v2)O(n^3v^2) 做法。
首先 exchange argument 一下可以知道确定扔掉哪些的时候，一定会按 bib_i 单调递减的顺序去做菜。
考虑如何对于给定的 aia_i 计算答案（bib_i 排序好了）。先二分，然后从前往后扫，将 aia_i 扔进一个 pq 里面。如果目前的前缀和加上 bib_i 比二分的值大了，那就弹出 pq 中最大的并不选他。容易理解这么做的正确性。
考虑经典 trick dp 维护 pq。枚举二分的值，设计 dpi,j,k,l,0/1/2dp_{i,j,k,l,0/1/2} 表示看到 ii，考虑所有我们打算不选的东西之后目前前缀和为 jj，不选了 kk 个，目前选不选的分界线为 ll。0/1/20/1/2 为辅助维度，分别表示目前没有见到任何 ll，见到了 ll 且全选了，见到了 ll 选了且有一段后缀没选。
注意这里我们不需要记录 pq 里面剩了多少数，因为是否弹出只跟是否会爆有关，就不用在 pq 清空的时候将 ll 变大了，每次判断 j+bi+lj+b_i+l 如果大于二分的值，那么相当于顶满了，就可以将 ll 转移到更大的位置。注意最后一维 11 可以转移到 ≥l\geq l 而 22 可以转移到 >l>l。
一个小问题是对于不删的位置，我们还需要保证 j+bij+b_i 小于等于二分的值，在这类转移的时候判一下即可。
这么做复杂度是 O(n4v3)O(n^4v^3) 的，感觉已经能过了。
考虑优化，注意到我们只在乎（二分的值不妨设为 limlim）lim−jlim-j 的值，让 nv+max⁡binv+\max b_i 次 dp 并行即可，总复杂度 O(n3v2)O(n^3v^2)。
统计答案是容易的，不再阐述。
CPP
#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;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...