题解：AT_arc207_a [ARC207A] Affinity for Artifacts

light_searcher · 2025-11-18 10:53:19 · 题解

首先做第一步转化，a_i = \max(a_i-i+1,0)+\min(a_i,i-1)，设 sum= \sum\limits_{i=1}^n a_i，那么 \sum\limits_{i=1}^n\max(a_i-i+1,0) \le x 就等价于 \sum\limits_{i=1}^n \min(a_i,i-1)\ge sum-x，令 x'=sum-x，则 x' 的有效范围是 \mathcal O(n^2) 的，这样就可以 dp 了。

把重排看作是 2n 个数匹配问题，具体来说，先如下构造序列 b：

称 b_1 \sim b_n 为一类点，b_{n+1} \sim b_{2n} 为二类点，则我们要把一类点和二类点两两一一配对。把 b 从小到大排序后，\min 的限制就被消除掉了。具体来说，如果 b_i,b_j,i<j 不是同类点，那么 b_i 和 b_j 配对的贡献是 b_i。

这样就可以开始 dp 了。设 f_{i,j,k,l} 表示前 i 个数，有 j 个一类点还没有匹配，k 个二类点还没有匹配，且当前贡献是 l 的方案数。

假设当前转移到的是 b_i，以 b_i 为一类点为例，二类点是相同的。

这个转移比较好理解，但是这样是 \mathcal O(n^5) 的，需要优化状态。

因为已经匹配了的一类点和二类点的数量总是相同，设 cnt_{i,0/1} 表示 b_1 \sim b_i 中的一类点和二类点的个数，那么如果 cnt_{i,0}-j \ne cnt_{i,1}-k，f_{i,j,k,l} 总是为 0。

那么把状态稍微改一下，设 f_{i,j,k} 表示前 i 个数，匹配了 j 对，即一类点未匹配的个数是 cnt_{i,0}-j，二类点未匹配的个数是 cnt_{i,1}-j，且当前贡献是 k 的方案数，转移类似，最后的答案是 \sum \limits_{i \ge x'} f_{2n,n,i}，时间复杂度是 \mathcal O(n^4) 的，最后再滚动数组优化一下空间即可。

代码：

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