JZOJ 5988 珂学计树题 【树->括号序列->01序列+Burside引理】

题面：

题目分析：

把树转成括号表示：
第一个左括号到第一个右括号之间的部分描述根节点的左子树.剩下的部分描述根节点的右子树.
”n个0,n个1的序列,循环移位后相同则本质相同”的等价类和”n对括号合法的括号序列”的等价类一一对应.
然后做法就看这里$\rarr$→Felix-Lee dalao的博客

burside引理和polya定理

Code：

#include<cstdio>
#define maxn 1000005
const int mod = 998244353;
int n,p[maxn/10],phi[maxn],fac[maxn<<1],inv[maxn<<1],ans;
bool v[maxn];
void Prime(int N){
	phi[1]=1;int m=0;
	for(int i=2;i<=N;i++){
		if(!v[i]) p[++m]=i,phi[i]=i-1;
		for(int j=1,k;j<=m&&(k=p[j]*i)<=N;j++){
			v[k]=1;
			if(i%p[j]==0) {phi[k]=phi[i]*p[j];break;}
			phi[k]=phi[i]*phi[p[j]];
		}
	}
}
void FAC_INV(int N){
	fac[0]=fac[1]=inv[0]=inv[1]=1;
	for(int i=2;i<=N;i++) fac[i]=1ll*fac[i-1]*i%mod,inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
	for(int i=2;i<=N;i++) inv[i]=1ll*inv[i]*inv[i-1]%mod;
}
int C(int n,int m){return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;}
inline int ksm(int a,int b){
	int s=1;
	for(;b;b>>=1,a=1ll*a*a%mod) if(b&1) s=1ll*s*a%mod;
	return s;
}
int main()
{
	//freopen("tree.in","r",stdin);
	//freopen("tree.out","w",stdout);
	scanf("%d",&n);
	Prime(n);
	FAC_INV(2*n);
	for(int i=1;i*i<=n;i++) if(n%i==0){
		ans=(ans+1ll*C(2*i,i)*phi[n/i])%mod;
		if(i*i!=n) ans=(ans+1ll*C(2*(n/i),n/i)*phi[i])%mod;
	}
	printf("%d\n",1ll*ans*ksm(2*n,mod-2)%mod);
}

我今天真的是跪了。。 连线性筛都要打错而且还看不出来（phi[i]*phi[p[j]]写成phi[i]*phi[j]）。。滚去睡觉。。