专栏文章

题解：AT_arc207_a [ARC207A] Affinity for Artifacts

llight_searcher
AT_arc207_a题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@min5vf5i
此快照首次捕获于
2025/12/01 21:04
3 个月前
此快照最后确认于
2025/12/01 21:04
3 个月前
查看原文
首先做第一步转化，ai=max⁡(ai−i+1,0)+min⁡(ai,i−1)a_i = \max(a_i-i+1,0)+\min(a_i,i-1)，设 sum=∑i=1naisum= \sum\limits_{i=1}^n a_i，那么 ∑i=1nmax⁡(ai−i+1,0)≤x\sum\limits_{i=1}^n\max(a_i-i+1,0) \le x 就等价于 ∑i=1nmin⁡(ai,i−1)≥sum−x\sum\limits_{i=1}^n \min(a_i,i-1)\ge sum-x，令 x′=sum−xx'=sum-x，则 x′x' 的有效范围是 O(n2)\mathcal O(n^2) 的，这样就可以 dp 了。
把重排看作是 2n2n 个数匹配问题，具体来说，先如下构造序列 bb：
bi={ai (1≤i≤n)i−n−1 (n<i≤2n)b_i = \left\{\begin{aligned} a_i \space (1 \le i \le n) \\ i-n-1 \space (n<i \le 2n) \end{aligned}\right.
称 b1∼bnb_1 \sim b_n 为一类点，bn+1∼b2nb_{n+1} \sim b_{2n} 为二类点，则我们要把一类点和二类点两两一一配对。把 bb 从小到大排序后，min⁡\min 的限制就被消除掉了。具体来说，如果 bi,bj,i<jb_i,b_j,i<j 不是同类点，那么 bib_i 和 bjb_j 配对的贡献是 bib_i。
这样就可以开始 dp 了。设 fi,j,k,lf_{i,j,k,l} 表示前 ii 个数，有 jj 个一类点还没有匹配，kk 个二类点还没有匹配，且当前贡献是 ll 的方案数。
假设当前转移到的是 bib_i，以 bib_i 为一类点为例，二类点是相同的。
  1. bib_i 和 ii 前面的二类点配对，fi,j,k,l←fi−1,j,k+1,l×jf_{i,j,k,l} \gets f_{i-1,j,k+1,l} \times j。
  2. bib_i 和 ii 后面的二类点配对，fi,j,k,l←fi−1,j−1,k,l−bif_{i,j,k,l}\gets f_{i-1,j-1,k,l-b_i}。
这个转移比较好理解，但是这样是 O(n5)\mathcal O(n^5) 的，需要优化状态。
因为已经匹配了的一类点和二类点的数量总是相同，设 cnti,0/1cnt_{i,0/1} 表示 b1∼bib_1 \sim b_i 中的一类点和二类点的个数，那么如果 cnti,0−j≠cnti,1−kcnt_{i,0}-j \ne cnt_{i,1}-k，fi,j,k,lf_{i,j,k,l} 总是为 00。
那么把状态稍微改一下，设 fi,j,kf_{i,j,k} 表示前 ii 个数，匹配了 jj 对，即一类点未匹配的个数是 cnti,0−jcnt_{i,0}-j，二类点未匹配的个数是 cnti,1−jcnt_{i,1}-j，且当前贡献是 kk 的方案数，转移类似，最后的答案是 ∑i≥x′f2n,n,i\sum \limits_{i \ge x'} f_{2n,n,i}，时间复杂度是 O(n4)\mathcal O(n^4) 的，最后再滚动数组优化一下空间即可。
代码：
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=105,mod=998244353;
int n,x,f[2][N][N*N],ans,sum,cnt[2];
pair<int,int>a[2*N];
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>x;
	for(int i=1;i<=n;i++) cin>>a[i].first,sum+=a[i].first,a[n+i]={i-1,1};
	sort(a+1,a+n*2+1);
	sum-=x;
	if(sum>n*(n-1)/2){
		cout<<0<<'\n';
		return 0;
	}
	if(sum<0){
		ans=1;
		for(int i=1;i<=n;i++) ans=ans*i%mod;
		cout<<ans<<'\n';
		return 0;
	}
	f[0][0][0]=1;
	for(int i=1;i<=2*n;i++){
		cnt[a[i].second]++;
		memset(f[i&1],0,sizeof(f[i&1]));
		int p=i&1,q=p^1;
		for(int j=0;j<=n;j++)
			for(int k=0;k<=n*(n-1)/2;k++){
				if(j) f[p][j][k]=1ll*(cnt[!a[i].second]-j+1)*f[q][j-1][k]%mod;
				if(k>=a[i].first) f[p][j][k]=(f[p][j][k]+f[q][j][k-a[i].first])%mod; 
			}
	}
	for(int i=sum;i<=n*(n-1)/2;i++) ans=(ans+f[0][n][i])%mod;
	cout<<ans<<'\n';
	return 0;
}

评论

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

正在加载评论...