题目链接

https://www.luogu.org/problem/P5564

题解

这题最重要的一步是读明白题。

为了方便起见下面设环长可以是\(1\), 最后统计答案时去掉即可。

实际上就相当于如果只有树没有环，答案就是卡特兰数第\((n-1)\)项。令\(C(x)\)为Catalan数生成函数，\(T(x)\)为这种树的生成函数，则\(T(x)=xC(x)\)。

然后环的话可以考虑Burnside引理，首先枚举环长，枚举置换，易得答案为\(\sum^n_{k=1}\frac{1}{k}\sum_{d|k,d|\gcd(a_i)}\phi(\frac{k}{d})[x^{\frac{nd}{k}}]T^d(x)\times \frac{(\frac{n}{d})!}{\prod^m_{i=1}(\frac{a_i}{d})!}=\sum_{d|\gcd(a_i)}\frac{\phi(d)(\frac{n}{d})!}{d\prod^m_{i=1}(\frac{a_i}{d})!}\sum^{\frac{n}{d}}_{k=1}[x^{\frac{n}{d}}]\frac{T^k(x)}{k}\)

然后有两种做法。

做法一

显然后面的\(\sum_{k=1}\frac{T^k}{k}=-\ln(1-T)\), 于是直接多项式\(\ln\)求出系数即可。

时间复杂度\(O(n\log n)\).

做法二

有没有优美一点的？

有一个非常神奇的结论: \([x^n]C^m(x)={2n+m-1\choose n}\frac{m}{n+m}\), 证明考虑卡特兰数的折线意义，当纵坐标首次变成\(-1\)时视为第二段拼接开始，可以把后面的都上移\(1\)位，再次变成\(-1\)时视为第三段开始，后面的都上移\(1\)位……直到最后，因此\(m\)段折线拼接的方案数就等于从\((0,0)\)走到\((2n+m-1,-m+1)\)的方案数。

于是\([x^n]T^m(x)={2n-m-1\choose n-m}\times\frac{m}{n}\), 带入原式可得\(\frac{1}{n}\sum_{d|\gcd(a_i)}\phi(d)\frac{(\frac{n}{d})!}{\prod(\frac{a_i}{d})!}\sum^{\frac{n}{d}}_{k=1}{\frac{2n}{d}-k-1\choose \frac{n}{d}-k}=\frac{1}{n}\sum_{d|\gcd(a_i)}\phi(d)\frac{(\frac{n}{d})!}{\prod(\frac{a_i}{d})!}{\frac{2n}{d}-1\choose \frac{n}{d}-1}\) (省略了很多中间步骤)

观察到我们只需要枚举\(\gcd(a_i)\)的约数，每个计算复杂度为\(O(m)\), 约数个数不超过\(\gcd(a_i)\le \min(a_i)\le \frac{n}{m}\), 故总复杂度为\(O(n)\).

orz myh&dcx

代码

做法二

#include<cstdio>

#include<cstdlib>

#include<iostream>

#include<cassert>

#define llong long long

using namespace std;

const int N = 4e5;

const int P = 998244353;

llong fact[N+3],finv[N+3];

int pri[N+3];

bool isp[N+3];

int phi[N+3];

int a[N+3];

int n,m,np;

void EulerSieve()

{

	isp[1] = true; phi[1] = 1;

	for(int i=2; i<=N; i++)

	{

		if(isp[i]==false) {pri[++np] = i; phi[i] = i-1;}

		for(int j=1; j<=np && i*pri[j]<=N; j++)

		{

			isp[i*pri[j]] = true;

			if(i%pri[j]==0) {phi[i*pri[j]] = phi[i]*pri[j]; break;}

			else {phi[i*pri[j]] = phi[i]*phi[pri[j]];}

		}

	}

}

int gcd(int x,int y) {return y==0?x:gcd(y,x%y);}

llong quickpow(llong x,llong y)

{

	llong cur = x,ret = 1ll;

	for(int i=0; y; i++)

	{

		if(y&(1ll<<i)) {y-=(1ll<<i); ret = ret*cur%P;}

		cur = cur*cur%P;

	}

	return ret;

}

llong mulinv(llong x) {return finv[x]*fact[x-1]%P;}

llong comb(llong x,llong y) {return x<0||y<0||x<y ? 0ll : fact[x]*finv[y]%P*finv[x-y]%P;}

llong calc(llong x)

{

	llong ret = fact[n/x];

	for(int i=1; i<=m; i++) ret = ret*finv[a[i]/x]%P;

	return ret;

}

int main()

{

	EulerSieve();

	fact[0] = 1ll; for(int i=1; i<=N; i++) fact[i] = fact[i-1]*i%P;

	finv[N] = quickpow(fact[N],P-2); for(int i=N-1; i>=0; i--) finv[i] = finv[i+1]*(i+1)%P;

	scanf("%d%d",&n,&m); int g = 0;

	for(int i=1; i<=m; i++) scanf("%d",&a[i]),g = gcd(a[i],g);

	llong ans = 0ll;

	for(int i=1; i<=n; i++)

	{

		if(g%i==0)

		{

			llong tmp = phi[i]*calc(i)%P*comb(n*2/i-1,n/i-1)%P;

			ans = (ans+tmp)%P;

		}

	}

	ans = ans*mulinv(n)%P;

	ans = (ans-comb(2*n-2,n-1)*mulinv(n)%P*calc(1)%P+P)%P;

	printf("%lld\n",ans);

	return 0;

}