专栏文章

题解：AT_abc387_g [ABC387G] Prime Circuit

__abcd_
AT_abc387_g题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqj6iyi
此快照首次捕获于
2025/12/04 05:40
3 个月前
此快照最后确认于
2025/12/04 05:40
3 个月前
查看原文

[ABC387G] Prime Circuit

我们注意到一个非常重要的性质：所有 >2> 2 的偶数都不是质数！
因此，假设图中有两个环，且他们有相同的点，那么将他们异或一下就能形成新的环。显然，在原来的两个环和新环中，至少有一个环的长度是偶数，这是不行的。因此图必须是一个仙人掌。
那题目就转换成：有标号仙人掌计数，且所有环的长度都是质数。如果所有环都已经确定下来了，那么就需要连若干条边将他们串成一个仙人掌。根据 prufer\rm prufer 序列，假设有 kk 个环，且第 ii 个环的长度为 sis_i，则一共有 nk−2∏i=1ksi=n−2∏i=1knsin^{k-2} \prod\limits_{i=1}^k s_i = n^{-2} \prod\limits_{i=1}^k n s_i 种串法。这就非常好算了！对于一个大小为 mm 的环，他的贡献就是 nmnm，而他的方案数是 (m−1)!2\frac{(m-1)!}{2}，当 m=1m=1 时方案数为 11。只需要把这个 EGF\rm EGF 做一个 exp⁡\exp 就行了。复杂度 O(nlog⁡n)O(n \log n)。
CPP
#include<bits/stdc++.h>
#define ll long long
#define pn putchar('\n')
#define mset(a,x) memset(a,x,sizeof a)
#define mcpy(a,b) memcpy(a,b,sizeof a)
#define all(a) a.begin(),a.end()
#define fls() fflush(stdout)
#define mod 998244353
#define int ll
#define maxn 250005
#define i2 499122177
#define N 524288
using namespace std;
int re()
{
    int x=0;
    bool t=1;
    char ch=getchar();
    while(ch>'9'||ch<'0')
        t=ch=='-'?0:t,ch=getchar();
    while(ch>='0'&&ch<='9')
        x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return t?x:-x;
}
int ksm(int x,int y)
{
    int ret=1;
    while(y)
    {
        if(y&1)ret=ret*x%mod;
        x=x*x%mod,y>>=1;
    }
    return ret;
}
void dq(int &x)
{
    if(x>=mod)x-=mod;
    if(x<0)x+=mod;
}
int n;
bool isnp[maxn];
vector<int>pr;
int phi[maxn],mu[maxn];
int jc[maxn],inv[maxn];
void zh_init()
{
    jc[0]=1;
    for(int i=1;i<=n;i++)
        jc[i]=jc[i-1]*i%mod;
    inv[n]=ksm(jc[n],mod-2);
    for(int i=n;i;i--)
        inv[i-1]=inv[i]*i%mod;
}
int A(int x,int y)
{
    if(x<y)return 0;
    return jc[x]*inv[x-y]%mod;
}
int C(int x,int y)
{
    return A(x,y)*inv[y]%mod;
}
void prime_init()
{
    mu[1]=phi[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!isnp[i])
        {
            pr.push_back(i);
            phi[i]=i-1;
            mu[i]=-1;
        }
        for(int j:pr)
        {
            int x=i*j;
            if(x>n)
                break;
            isnp[x]=1;
            if(i%j==0)
            {
                mu[x]=0;
                phi[x]=phi[i]*j;
                break;
            }
            mu[x]=-mu[i];
            phi[x]=phi[i]*(j-1);
        }
    }
}
namespace polynomial
{
    int gn[N<<1],gi[N<<1],rev[N<<1],iv[N+1];
    void poly_init()
    {
        for(int i=1;i<=N;i<<=1)
        {
            gn[i]=ksm(3,(mod-1)/i);
            gi[i]=ksm(gn[i],i-1);
        }
        gn[0]=gi[0]=1;
        for(int i=1;i<N<<1;i++)
        {
            int j=1<<__lg(i);
            gn[i]=gn[i-1]*gn[j]%mod;
            gi[i]=gi[i-1]*gi[j]%mod;
        }
        for(int i=2;i<=N;i<<=1)
        {
            for(int j=i;j<i<<1;j++)
            {
                rev[j]=rev[j-i>>1|i]>>1;
                if(j&1)
                    rev[j]|=i>>1;
            }
        }
        iv[0]=iv[1]=1;
        for(int i=2;i<=N;i++)
            iv[i]=(mod-mod/i)*iv[mod%i]%mod;
    }
    int getn(int n)
    {
        return n==1?1:1<<__lg(n-1)+1;
    }
    struct Poly
    {
        int a[N];
        int& operator [] (int x)
        {
            return a[x];
        }
        void print(int n,int l=0)
        {
            for(int i=l;i<l+n;i++)
                printf("%lld ",a[i]);
            pn;
        }
        void cpy(Poly& t,int n,int l=0)
        {
            for(int i=l;i<l+n;i++)
                a[i]=t[i];
        }
        void clr(int n,int l=0)
        {
            for(int i=l;i<l+n;i++)
                a[i]=0;
        }
        void NTT(int n,int ty=1)
        {
            for(int i=0,*t=rev+n;i<n;i++,t++)
            {
                if(*t<i)
                    swap(a[i],a[*t]);
            }
            for(int i=1;i<n;i<<=1)
            {
                for(int j=0;j<n;j+=i<<1)
                {
                    int *x=(ty==1?gn:gi)+(i<<1)-1;
                    for(int k=j;k<j+i;k++,x++)
                    {
                        int l=a[k],r=*x*a[k+i]%mod;
                        a[k]=l+r,a[k+i]=l-r;
                        a[k]=a[k]>=mod?a[k]-mod:a[k];
                        a[k+i]=a[k+i]<0?a[k+i]+mod:a[k+i];
                    }
                }
            }
            if(ty==-1)
            {
                for(int i=0;i<n;i++)
                    a[i]=a[i]*iv[n]%mod;
            }
        }
        void mul(Poly& F,Poly& G,int n)
        {
            n=getn(n);
            F.NTT(n);
            G.NTT(n);
            for(int i=0;i<n;i++)
                a[i]=F[i]*G[i]%mod;
            NTT(n,-1);
        }
        void bni(Poly& t,int n)
        {
            if(n==1)
            {
                a[0]=ksm(t[0],mod-2);
                return;
            }
            clr(n>>1,n>>1);
            static Poly tni1,tni2;
            tni1.cpy(*this,n);
            tni2.cpy(t,n);
            tni1.mul(tni1,tni2,n);
            tni1.clr(n>>1);
            tni2.cpy(*this,n);
            tni1.mul(tni1,tni2,n);
            for(int i=n>>1;i<n;i++)
                dq(a[i]=-tni1[i]);
        }
        void ni(int n)
        {
            static Poly tni0;
            n=getn(n);
            tni0.cpy(*this,n);
            for(int i=1;i<=n;i<<=1)
                bni(tni0,i);
        }
        void dao(int n)
        {
            for(int i=1;i<n;i++)
                a[i-1]=i*a[i]%mod;
            a[n-1]=0;
        }
        void jf(int n)
        {
            for(int i=n-1;i;i--)
                a[i]=a[i-1]*iv[i]%mod;
            a[0]=0;
        }
        void ln(int n)
        {
            static Poly tln;
            n=getn(n);
            tln.cpy(*this,n<<1);
            tln.dao(n);
            ni(n);
            mul(*this,tln,n<<1);
            jf(n);
        }
        void exp(int n)
        {
            n=getn(n);
            static Poly texp0;
            texp0.cpy(*this,n);
            a[0]=1;
            a[1]=0;
            for(int len=2;len<=n;len<<=1)
            {
                static Poly texp1,texp2,texp3;
                texp1.bni(*this,len>>1);
                texp1.bni(*this,len);
                texp2.cpy(texp1,len);
                texp3.cpy(*this,len);
                texp3.dao(len);
                texp3.clr(len,len);
                texp2.clr(len,len);
                texp2.mul(texp2,texp3,len<<1);
                texp2.jf(len);
                dq(texp2[0]=1-texp2[0]);
                for(int i=1;i<len;i++)
                    dq(texp2[i]=texp0[i]-texp2[i]);
                clr(len,len);
                mul(*this,texp2,len<<1);
                clr(len,len);
                texp1.clr(len,len);
            }
        }
        void mi(int n,int m)
        {
            n=getn(n);
            ln(n);
            for(int i=0;i<n;i++)
                (a[i]*=m)%=mod;
            exp(n);
        }
    }F;
}
using namespace polynomial;
signed main()
{
    poly_init();
    n=re();
    prime_init();
    zh_init();
    F[1]=n;
    for(int i=3;i<=n;i++)
    {
        if(!isnp[i])
            F[i]=i2*n%mod;
    }
    F.exp(n+1);
    printf("%lld\n",F[n]*jc[n]%mod*ksm(n*n%mod,mod-2)%mod);
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...