题解：AT_arc207_a [ARC207A] Affinity for Artifacts

FS_NEO · 2025-10-29 12:10:36 · 题解

记录伟大的 Trick。

首先我们注意到，无论怎么转换，最终答案至多与 \sum{a_i} 相差 n^2。于是我们可以将合法性转换成关于偏移量的，即 \sum{\min(i-1,a_{p_i})} \ge S-x。对于这种取 \min 的计数有一 trick，即将 \min 内所有数排序，考虑配对方案数。于是 DP 时记录还剩多少个数没配上对，新数放左半边直接影响和，配右半边则不影响答案。转移是简单的。

Code :

/*

        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;
}