题解：AT_arc207_a [ARC207A] Affinity for Artifacts

记录伟大的 Trick。

首先我们注意到，无论怎么转换，最终答案至多与

\sum{a_i}

相差

n^2

。于是我们可以将合法性转换成关于偏移量的，即

\sum{\min(i-1,a_{p_i})} \ge S-x

。对于这种取

\min

的计数有一 trick，即将

\min

内所有数排序，考虑配对方案数。于是 DP 时记录还剩多少个数没配上对，新数放左半边直接影响和，配右半边则不影响答案。转移是简单的。

Code :

CPP

/*

		2025.10.25

  * Happy Zenith Noises *

*/
#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pb push_back
#define RG register
using namespace std;
typedef pair<int,int>P;
typedef pair<int,P>PP;
typedef unordered_map<int,int>ump;
const int MAXN=105,mod=998244353,inf=0x3f3f3f3f3f3f3f3f;
int n,x,s;
P a[MAXN*2];
int f[MAXN*2][MAXN][MAXN*MAXN],ans,L[MAXN*2],R[MAXN*2];
void add(int &x,int y){x=(x+y)%mod;}
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].fi,a[i].se=0,s+=a[i].fi,a[i+n].fi=i-1,a[i+n].se=1;
	sort(a+1,a+1+n*2);
	for(int i=1;i<=n*2;i++)L[i]=L[i-1]+(a[i].se==0),R[i]=R[i-1]+(a[i].se==1);
	f[0][0][0]=1;
	for(int i=1;i<=n*2;i++){
		for(int j=0;j<=n;j++){
			int j1=R[i-1]-(L[i-1]-j);
			for(int k=0;k<=n*n;k++){
				if(!f[i-1][j][k])continue;
				if(a[i].se){
					if(k+a[i].fi<=n*n)add(f[i][j][k+a[i].fi],f[i-1][j][k]);
					if(j>0)add(f[i][j-1][k],f[i-1][j][k]*j%mod);
				}
				else{
					if(k+a[i].fi<=n*n)add(f[i][j+1][k+a[i].fi],f[i-1][j][k]);
					if(j1>0)add(f[i][j][k],f[i-1][j][k]*j1%mod);
				}
			}
		}
	}
	for(int i=max(0ll,s-x);i<=n*n;i++)add(ans,f[n*2][0][i]);
	cout<<ans;
	return 0;
}

题解：AT_arc207_a [ARC207A] Affinity for Artifacts

文章操作

相关推荐

评论

题解：AT_arc207_a [ARC207A] Affinity for Artifacts