题目描述

群里有\(k\)个不同的复读机。为了庆祝平安夜的到来，在接下来的\(n\)秒内，它们每秒钟都会选出一位优秀的复读机进行复读。非常滑稽的是，一个复读机只有总共复读了\(d\)的倍数次才会感到快乐。问有多少种不同的安排方式使得所有的复读机都感到快乐。

Sol

发现 \(d\) 只有 \(3\) ，很可能需要分开讨论。

\(d=1\) 就是 \(k^n\)

\(d=2\):

其实容易发现这是一个有次数限制的可重排列问题，那么可以使用指数型生成函数来解决。

一个复读机的生成函数就是:

\[G(x)=\sum_{i=0} \frac{x^{2i}}{(2i)!}
\]

其实就是去除掉所有奇数项，那么这是一个常见的套路了，就是:

\[G(x)=\frac{e^x+e^{-x}}{2}
\]

泰勒展开后作差就是原来的式子了。

我们要求的东西就是:

\[n!*G(x)^k[x^n]
\]

这里直接二项式定理展开:

\[n!\bigg(\frac{(e^x+e^{-x})^k}{2^k}\bigg)=n!\bigg(\frac{\sum_{i=0}^k e^{(2i-k)x}{k\choose i}}{2^k}\bigg)
\]

里面泰勒逆展开后发现 \([x^n]\) 下自带一个 \(n!\) ，所以最后的答案就是:

\[\frac{\sum_{i=0}^k (2i-k)^n{k\choose i}}{2^k}
\]

\(d=3\):

仿照上面的式子有:

\[G(x)=\sum_{i=0} \frac{x^{3i}}{(3i)!}
\]

无法使用常规方法化简。那么我们要使用一种更为本质的方法。

式子可以写成这样:

\[G(x)=\sum_{i=0}[3|i]\frac{x^{i}}{i!}
\]

用上单位根的性质：

\[G(x)=\sum_{i=0}\frac{1}{3}\sum_{j=0}^2 \frac{w_3^{ji}x^i}{i!}
\]

这之后常规套路移项然后合并次数

\[G(x)=\frac{1}{3}\sum_{j=0}^2 \sum_{i=0}\frac{(w_3^jx)^i}{i!}
\]

所以又可以泰勒逆展开了:

\[G(x)=\frac{1}{3}\sum_{j=0}^2 e^{w_3^jx}
\]

容易发现这个形式和 \(d=2\) 的相同，因为 \(d=2\) 做法的本质也是单位根反演，只不过因为单位根是 +-1 所以很容易手动容斥出来。

还是要求:

\[n!G(x)^k[x^n]
\]

直接展开:

\[n!G(x)^k=n!\dfrac{\sum_{i_0+i_1+i_2=k}(e^{(i_0w_3^0+i_1w_3^1+i_2w_3^2})x)\frac{k!}{i_0!i_1!i_2!}}{3^k}
\]

一样的泰勒逆展开然后取 \([x^n]\)，最后的答案式就是：

\[\dfrac{\sum_{i_0+i_1+i_2=k} (i_0w_3^0+i_1w_3^1+i_2w_3^2) \frac{k!}{i_0!i_1!i_2!}}{3^k}
\]

单位根用原根代替就行了。

code:

#include<bits/stdc++.h>

#define Set(a,b) memset(a,b,sizeof(a))

using namespace std;

const int N=5e5+10;

const int mod=19491001;

const int inv2=(mod+1)/2;

template <typename T> inline void init(T&x){

	x=0;char ch=getchar();bool t=0;

	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') t=1;

	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+(ch-48);

	if(t) x=-x;return;

}

typedef long long ll;

template<typename T>inline void Inc(T&x,int y){x+=y;if(x>=mod) x-=mod;return;}

template<typename T>inline void Dec(T&x,int y){x-=y;if(x <  0) x+=mod;return;}

template<typename T>inline int fpow(int x,T k){int ret=1;for(;k;k>>=1,x=(ll)x*x%mod) if(k&1) ret=(ll)ret*x%mod;return ret;}

inline int Sum(int x,int y){x+=y;if(x>=mod) return x-mod;return x;}

inline int Dif(int x,int y){x-=y;if(x < 0 ) return x+mod;return x;}

int n,k,d;

int fac[N],finv[N];

inline void Sieve(int N){

	fac[0]=finv[0]=fac[1]=finv[1]=1;

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

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

	return;

}

inline int C(int n,int m){return n<m? 0:((ll)fac[n]*finv[m]%mod*finv[n-m]%mod);}

inline int Getroot(int mod){

	static int pri[50];int x=mod-1;int cnt=0;

	for(int i=2;i*i<=x;++i){

		if(x%i==0) {

			pri[++cnt]=i,x/=i;while(x%i==0) x/=i;

		}

	}

	for(int g=2;;++g){

		bool fl=1;

		for(int i=1;i<=cnt;++i) if(fpow(g,(mod-1)/pri[i])==1) {fl=0;break;}

		if(fl) return g;

	}return 0;

}

int main()

{

	init(n),init(k),init(d);

	if(d==1) cout<<fpow(k,n)<<endl;

	else {

		Sieve(k);

		if(d==2) {

			int ans=0;

			for(int i=0;i<=k;++i) Inc(ans,(ll)fpow(2*i-k,n)*C(k,i)%mod);

			ans=(ll)ans*fpow(inv2,k)%mod;

			cout<<ans<<endl;

		}else{

			int ans=0;int g=Getroot(mod);

			int w0=1,w1=fpow(g,(mod-1)/3),w2=(ll)w1*w1%mod;

			for(int i0=0;i0<=k;++i0) {

				for(int i1=0;i1<=k;++i1){

					if(i0+i1>k) break;

					int i2=k-i0-i1;

					Inc(ans,(ll)fpow(((ll)i0*w0%mod+(ll)i1*w1%mod+(ll)i2*w2%mod)%mod,n)*fac[k]%mod*finv[i0]%mod*finv[i1]%mod*finv[i2]%mod);

				}

			}

			ans=(ll)ans*fpow(3,(ll)(mod-2)*k%(mod-1))%mod;

			cout<<ans<<endl;

		}

	}

	return 0;

}

巴特西

【UOJ#450】[集训队作业2018] 复读机

题目描述

Sol

最新文章

热门文章