20241114_KCR_互测

考试总结

T1

全场唯一可做题，虽然场上想歪了

设 $f_{i,j}$ 表示现在取完了 $1$ 到 $i$ 的点组成图，环的大小的 $\mathrm lcm$ 为 $j$ 的贡献和

显然答案与编号无关的，于是我们可以枚举当前编号最大点所在环的大小转移，既然答案与编号无关，那么答案就分成了两部分：一边是一个环，这一部分是好处理的，等会再说

另一部分是一个相同的子问题，可能会感觉好像这个结构不一样因为你选之后点编号已经乱了，但是由于答案和编号无关所以直接重新编号是一样的不是吗

于是左半边的子问题就是 $f_{i-len,lcm'}$ ，可以用set来辅助转移，用 $dp$ 实现从而减小无用状态的访问，这样复杂度就正确了，可过

一种可能的实现：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=105;
const int mod=998244353;
int inv[N],fac[N],finv[N];
int C(int n,int m){
    return (fac[n]*finv[n-m]%mod)*finv[m]%mod;
}
typedef pair<int,int> pii;
int n,k;
int qpow(int a,int b){
    int ret=1;
    while(b){
        if(b&1) ret=(ret*a)%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ret;
}
void init(){
    inv[0]=inv[1]=fac[0]=fac[1]=finv[0]=1;
    for(int i=2;i<=100;i++)
        inv[i]=inv[mod%i]*(mod-mod/i)%mod;
    for(int i=1;i<=100;i++){
        fac[i]=fac[i-1]*i%mod;
        finv[i]=finv[i-1]*inv[i]%mod;
    }
}
#define mk make_pair
set<pii> S[N];
int LCM(int a,int b){
    return a*b/__gcd(a,b);
}
void modi(int pos,int lcm,int cnt){
    auto it=S[pos].upper_bound(mk(lcm,0));
    if(it==S[pos].end() or (*it).first!=lcm){S[pos].insert(mk(lcm,cnt));return ;}
    cnt=cnt+(*it).second,cnt%=mod;
    S[pos].erase(it);
    S[pos].insert(mk(lcm,cnt));
}
signed main(){
    freopen("aporia.in", "r", stdin);
    freopen("aporia.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    init();
    cin>>n>>k;
    if(k==0){
        cout<<fac[n];
        return 0;
    }
    S[1].insert(mk(1,1));
    for(int i=2;i<=n;i++){
        S[i].insert(mk(i,fac[i-1]));
        for(int j=1;j<i;j++){
            int cnt=C(i-1,j-1)*fac[j-1]%mod;
            for(auto I:S[i-j]){
                int tot=I.second*cnt%mod;
                int lm=LCM(I.first,j);
                modi(i,lm,tot);
            }
        }
    }
    int ans=0;
    for(auto I:S[n]){
        ans=(ans+I.second*qpow(I.first,k)%mod)%mod;
    }
    cout<<ans;
}

感觉还有别的做法，比如刚下考xzy爷爷说他是根据分拆数什么做的，做题思路应该是不唯一的，但是这样应该是比较简单的吧

后三题选择性放弃了，不太可改