题解：CF1844H Multiple of Three Cycles

· · 题解

伟大的题目。

题意很简洁，让我们对所有只包含长度为 3 的倍数的环的排列计数，动态修。

显然，一个缺数的排列是若干条链和若干个环。除去已经确定的环，我们要算把剩下的链拼在一起的方案数。可以按模 3 的余数分成 0,1,2 三类，每类仅有一个属性：数量。令第 i 类数量为 cnt_i。

观察一下，0 是很特殊的，加上它不改变某个环的大小。考虑先算出 1 和 2 的方案数 k，然后对每个 0，考虑其加到哪条链后面。显然任意链都行。每加入一个 0，后来的 0 的选择就多一种，所以答案

=(cnt_1+cnt_2)\times(cnt_1+cnt_2+1)\times(cnt_1+cnt_2+2)\times ... =\frac {k(cnt_0+cnt_1+cnt_2)!}{(cnt_1+cnt_2)!}

于是考虑算 k。我们定义函数 g(x,y)，表示 cnt_1=x,cnt_2=y 时 k 的值。直接算式子是非常难做的，而且算出来不一定能维护。但是我们可以找递推关系。

为了不重不漏，先为所有 1 和 2 钦定一个序，每次选取序最小的链做操作。

有两条路，选 1 或 2。假定选 1，有两种情况：

于是就有式子：

g(x,y)=(x-1)g(x-2,y+1)+y(x+y-1)g(x-1,y-1)

若是选 2，按这个思路再分讨，又有：

g(x,y)=(y-1)g(x+1,y-2)+x(x+y-1)g(x-1,y-1)

这是很特殊的，因为它有两条转移线路。

再得不出什么性质了，我们选择性地把这个函数转移脉络画出来，尽量少用格子：

有个非常亮眼的结构！两条斜向上的线可以互相递推。

进一步地，我们可以实现顺着推，能不能倒着呢？因为只需知道两个相关格子的值，就能推出另一个。

这样就实现的斜线间的跳跃。

而题目要我们维护的，恰好是一条路径，与这个转移是很兼容的。

总结整理一下规律，我们可以得出这样的方法：

细节：反向遍历操作，可以从 (1,1) 和 (2,2) 开始转移。

时间复杂度 O(n) 。

:::success[代码]

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=3e5+7,mod=998244353;
int n,m,k[N],x[N],f[N],sz[N],d,a[N][3],cnt[3];
//ll g,g_;//(1,1),(2,2)
ll ans[N],mul[N],mul_[N],inv[N];
bool op;
struct node{
    ll a,b,x;
}g,g_;
inline ll f_pow(ll a,ll b){
    ll w=a,ans=1;
    while(b){
        if(b&1) ans*=w,ans%=mod;
        w*=w,w%=mod,b>>=1;
    }
    return ans;
}
inline int find(int x){
    if(f[x]==x) return x;
    return f[x]=find(f[x]);
}
inline node L(){
    return {g.a-1,g.b+2,
    (g_.x+((ll)mod-g.x)*g_.b%mod*(g_.a+g_.b-1))%mod*
    inv[g.a]%mod};
}
inline node R(){
    return {g.a+2,g.b-1,
    (g_.x+((ll)mod-g.x)*g_.a%mod*(g_.a+g_.b-1))%mod*
    inv[g.b]%mod};
}
inline node Rup(node x,node y){
    return {x.a+1,x.b+1,(x.x*(x.a+x.b+1)%mod*(x.a+1)+
    y.x*(y.b+1)%mod)%mod};
}
inline node Lup(node x,node y){
    return {x.a+1,x.b+1,(x.x*(x.a+x.b+1)%mod*(x.b+1)+
    y.x*(y.a+1)%mod)%mod};
}
inline bool merge(int u,int v){
    u=find(u),v=find(v);
    if(u==v) return sz[u]%3==0;
    f[u]=v,sz[v]+=sz[u];return 1;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    mul[0]=mul_[0]=1;
    for(int i=1;i<N;i++){
        inv[i]=f_pow(i,mod-2);
        mul[i]=(mul[i-1]*i)%mod;
        mul_[i]=f_pow(mul[i],mod-2);
    }
    cin>>n,op=1,a[0][1]=n,cnt[1]+=n;
    for(int i=1;i<=n;i++) f[i]=i,sz[i]=1;
    for(int i=1;i<=n;i++){
        cin>>k[i]>>x[i];
        a[i][(sz[find(k[i])])%3]--;
        a[i][(sz[find(x[i])])%3]--;
        a[i][(sz[find(k[i])]+sz[find(x[i])])%3]++;
        op&=merge(k[i],x[i]);
        if(op){
            cnt[0]+=a[i][0],cnt[1]+=a[i][1];
            cnt[2]+=a[i][2],d=i;
        }
    }
    g={1,1,1},g_={2,2,2+6};
    int x=cnt[1],y=cnt[2];
    if(x<y){
        for(int i=1;i<(y+2*x)/3;i++){
            g=Lup(g_,Rup(L(),g_)),swap(g,g_); 
        }
        for(int i=0;i<(y-x)/3;i++){
            node tmp=L();
            g_=Rup(tmp,g_),g=tmp;
        }
    }
    else{
        for(int i=1;i<(2*y+x)/3;i++){
            g=Lup(g_,Rup(L(),g_)),swap(g,g_); 
        }
        for(int i=0;i<(x-y)/3;i++){
            node tmp=R();
            g_=Lup(tmp,g_),g=tmp;
        }
    }
    while(!cnt[1]&&!cnt[2]){
        ans[d]=mul[cnt[0]];
        cnt[1]-=a[d][1],cnt[2]-=a[d][2];
        cnt[0]-=a[d][0],d--;
    }
    for(int i=d;i>=1;i--){
        ans[i]=g.x*mul[cnt[0]+cnt[1]+cnt[2]]%mod
        *mul_[cnt[1]+cnt[2]]%mod;
        if(a[i][1]==-1&&a[i][2]==-1){
            if(g.a>g.b) g=Lup(g_,Rup(L(),g_)),swap(g,g_);
            else g=Rup(g_,Lup(R(),g_)),swap(g,g_);
        }
        else if(a[i][1]==-2){
            node tmp=R();
            g_=Lup(tmp,g_),g=tmp;
        }
        else if(a[i][2]==-2){
            node tmp=L();
            g_=Rup(tmp,g_),g=tmp;
        }
        cnt[1]-=a[i][1],cnt[2]-=a[i][2];
        cnt[0]-=a[i][0];
    }
    for(int i=1;i<=n;i++) cout<<ans[i]<<"\n";
    return 0;
}

:::