题解 P5818 【[JSOI2011]同分异构体计数】
George1123
·
·
题解
到这里欺负老年退役选手 \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 种。f(x)\leftarrow t(x)^k。
-
翻转，共 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)。
-
旋转，共 k-1 种。设旋转节为 d，设 g=\gcd(d,k)，f(x)\leftarrow t(x^{k/g})^{g}。
$\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)$。
---
## 代码
```cpp
#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;
}
```
---
**祝大家学习愉快！**