LGP4916题解

第一眼，Burnside 直接丢上去啊。

设 \(f(n,m)\) 是有 \(n-m\) 个白色珠子和 \(m\) 个白色珠子的满足题意的环的个数，容易得到答案是：

\[\sum_{d|n,d|m}f(\frac{n}{d},\frac{m}{d})\varphi(d)
\]

考虑左边这个 \(f\) 怎么做。

我们将环断开，枚举前缀和后缀的黑色珠子个数，有：

\[f(n,m)=\sum_{x+y\leq k,x+y+2\leq n}g(n-x-y-1,m-x-y)=\sum_{i=0}^{\min(k,n-2)}(i+1)\times g(n-i-1,m-i)
\]

其中 \(g(n,m)\) 为不存在超过 \(k\) 个连续黑色珠子的序列个数，且序列的最后一个元素是白色的。

我们似乎可以接受单次 \(O(n\log n)\) 计算 \(f\) 的算法。

考虑上生成函数。我们强制钦定每一段黑珠子后面跟上一个白珠子（包括 \(0\) 个白珠子），那么一段的 OGF 就是 \(\sum_{i=0}^{k}x^i=\frac{1-x^{k+1}}{1-x}\)。

\(g\) 的单点就是 \(g(n,m)=[x^m](\frac{1-x^{k+1}}{1-x})^{n-m}\)。

写开：

\[g(n,m)=[x^m]\frac{1}{(1-x)^{n-m}}\times(1-x^{k+1})^{n-m}
\]

\[[x^m](\sum \binom{i+n-m-1}{i})\times(\sum_{i=0}^{n-m}\binom{n-m}{i}x^{(n-m)(k+1)})
\]

注意到你在单次处理时，这个 \(n-m\) 是一直不会变的。变的是多项式取哪一项。

直接把这两个东西写开，卷一下就好了。

我们再观察一下：

设 \(F(x)=\frac{1-x^{k+1}}{1-x}\)。

\[[x^m]\sum_{i=0}^k(i+1)x^iF^{n-m-1}(x)
\]

\[[x^m](xF'(x)+F(x))F^{n-m-1}(x)
\]

\[[x^m]xF'(x)F^{n-m-1}(x)+F^{n-m}(x)
\]

\[([x^{m-1}]F'(x)F^{n-m-1}(x))+([x^m]F^{n-m}(x))
\]

\[(\frac{1}{n-m}[x^{m-1}](F^{n-m}(x))')+([x^m]F^{n-m}(x))
\]

\[(\frac{m}{n-m}[x^m]F^{n-m}(x)))+([x^m]F^{n-m}(x))
\]

\[\frac{n}{n-m}[x^m]F^{n-m}(x)
\]

右边简单。

\[[x^m]\frac{(1-x^{k+1})^{n-m}}{(1-x)^{n-m}}
\]

\[[x^m](\sum_{i=0}\binom{i+n-m-1}{i}x^i)(\sum_{i=0}^{n-m}\binom{n-m}{i}(-1)^{i}x^{i(k+1)})
\]

\[\sum_{i=0}^{n-m}\binom{n-m}{i}(-1)^i\binom{m-i(k+1)+n-m-1}{n-m-1}
\]

然后就能够线性求单点的 \(f\) 了。

#include<cstdio>

const int M=1e5+5,mod=998244353;

int n,m,k,fac[M],ifac[M];

inline int pow(int a,int b){

	int ans(1);for(;b;b>>=1,a=1ll*a*a%mod)if(b&1)ans=1ll*ans*a%mod;return ans;

}

inline int C(const int&n,const int&m){

	return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;

}

inline int phi(int n){

	int ans(1);

	for(int i=2;i<=n;++i)if(!(n%i)){

		ans*=i-1;n/=i;while(!(n%i))ans*=i,n/=i;

	}

	return ans;

}

inline int f(const int&n,const int&m){

	int ans(0);

	for(int i=0;i<=n-m;++i){

		if(m-i*(k+1)<0)break;

		if(i&1)ans=(ans+1ll*(mod-C(n-m,i))*C(m-i*(k+1)+n-m-1,n-m-1))%mod;

		else ans=(ans+1ll*C(n-m,i)*C(m-i*(k+1)+n-m-1,n-m-1))%mod;

	}

	return 1ll*n*pow(n-m,mod-2)%mod*ans%mod;

}

signed main(){

	int ans(0);

	scanf("%d%d%d",&n,&m,&k);

	if(n==m)return printf("%d",m<=k),0;

	fac[0]=fac[1]=ifac[0]=ifac[1]=1;

	for(int i=2;i<=n;++i)fac[i]=1ll*fac[i-1]*i%mod,ifac[i]=1ll*(mod-mod/i)*ifac[mod%i]%mod;

	for(int i=2;i<=n;++i)ifac[i]=1ll*ifac[i-1]*ifac[i]%mod;

	for(int i=1;i<=n;++i)if(!(n%i)&&!(m%i))ans=(ans+1ll*f(n/i,m/i)*phi(i))%mod;

	printf("%d",1ll*ans*pow(n,mod-2)%mod);

}

巴特西

LGP4916题解

最新文章

热门文章