自动搬运

查看原文

来自洛谷，原作者为

	George1123 **

搬运于2025-08-24 22:14:38，当前版本为作者最后更新于2020-12-23 13:37:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

到这里欺负老年退役选手 $\to$ George1123

题面

JSOI2011 同分异构体计数

求有多少个本质不同的无向图基环树，有 $n$ 个点且环上的点数 $\le m$。答案对 $p$ 取模。

数据范围：$3\le n\le 1000$，$3\le m\le 50$，$10^4\le p\le 2\times 10^9$。

题解

设 $t(x)$ 为根节点子节点数 $\le 2$，所有节点子节点数 $\le 3$ 的本质不同无标号有根树个数。

这个东西不需要多项式，直接 Burnside 定理然后 dp 即可，参考 烷基计数 加强版。

然后枚举环长，设为 $k$，设当前答案多项式为 $\frac{f(x)}{2k}$。

利用 Burnside 定理，考虑 $G$ 的元素：

1. 不动，共 $1$ 种。$f(x)\leftarrow t(x)^k$。

2. 翻转，共 $k$ 种（即环不考虑外向树的对称轴个数，想象一下翻转后的置换环数即可）。

   • 假设 $k$ 是奇数 $f(x)\leftarrow t(x^2)^{\lfloor k/2\rfloor}t(x)$。
   • 假设 $k$ 是偶数 $f(x)\leftarrow \frac{1}{2}(t(x^2)^{k/2}+t(x^2)^{k/2-1}t(x)^2)$。

3. 旋转，共 $k-1$ 种。设旋转节为 $d$，设 $g=\gcd(d,k)$，$f(x)\leftarrow t(x^{k/g})^{g}$。

$n,m$ 很小，这部分不用多项式也可以实现：

$\Theta(n^2 m)$ 暴力卷积预处理出 $t(x)^a$。

上面的 $t(x^s)^a[x^n]=t(x)^a[x^{n/s}]$，也可以求了。

总时间复杂度 $\Theta(n^2 m+m^2\log m)$。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define x first
#define y second
#define bg begin()
#define ed end()
#define pb push_back
#define mp make_pair
#define sz(a) int((a).size())
#define R(i,n) for(int i(0);i<(n);++i)
#define L(i,n) for(int i((n)-1);i>=0;--i)
const int iinf=0x3f3f3f3f;
const ll linf=0x3f3f3f3f3f3f3f3f;

//Data
const int N=1001,M=51;
int n,m,mod,f[N],g[N],t[N],p[M][N];

//Math
int& fmod(int &x){return x+=x>>31&mod;}
int gcd(int a,int b){return a?gcd(b%a,a):b;}
int mypow(int a,int x=mod-2,int res=1){
    for(;x;x>>=1,a=1ll*a*a%mod)
        (x&1)&&(res=1ll*res*a%mod);
    return res;
}

//Main
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>mod,f[0]=p[0][0]=1;
    const int i6=mypow(6),i2=mypow(2);
    for(int i=1;i<=n;i++){
        R(a,i)  g[i]=(1ll*f[a]*f[i-1-a]+g[i])%mod;
        R(a,i)  f[i]=(1ll*f[a]*g[i-a]+f[i])%mod;
        for(int a=0;(a<<1)<i;a++)
            f[i]=(3ll*f[a]%mod*f[i-1-(a<<1)]+f[i])%mod;
        if((i-1)%3==0) f[i]=(2ll*f[(i-1)/3]+f[i])%mod;
        f[i]=1ll*f[i]*i6%mod,t[i]=g[i];
        if(i&1) t[i]=(f[(i-1)>>1]+t[i])%mod;
        t[i]=1ll*t[i]*i2%mod;
        // cout<<"i="<<i<<" t="<<t[i]<<'\n';
    }
    R(k,m)R(i,n+1)R(j,n+1-i)
        p[k+1][i+j]=(1ll*p[k][i]*t[j]+p[k+1][i+j])%mod;
    int ns=0;
    for(int k=3;k<=m;k++){
        int res=p[k][n]; // cout<<res<<'\n';
        if(k&1) for(int a=0;(a<<1)<=n;a++)
            res=(1ll*k*p[k>>1][a]%mod*t[n-(a<<1)]+res)%mod;
        else {
            if(~n&1) res=(1ll*(k>>1)*p[k>>1][n>>1]+res)%mod;
            for(int a=0;(a<<1)<=n;a++)
                res=(1ll*(k>>1)*p[(k>>1)-1][a]%mod
                    *p[2][n-(a<<1)]+res)%mod;
        }
        for(int d=1,G;d<k;d++)if(n%(k/(G=gcd(d,k)))==0)
            res=(0ll+p[G][n/(k/G)]+res)%mod;
        ns=(1ll*res*mypow(k<<1)+ns)%mod;
    }
    cout<<ns<<'\n';
    return 0;
}

祝大家学习愉快！