题意
有$ k$台复读机，每时每刻有且只有一台复读机进行复读
求$ n$时刻后每台复读机的复读次数都是$ d$的倍数的方案数
$ 1\leq d \leq 3,k \leq 5·10^5,n \leq 10^9$
当$ d=3$时$ k \leq 10^3$
题解
$ d=1$的略过
对复读机构建生成函数
发现这是指数生成函数
即我们要计算的是$$(\sum_{i=0}^n[d|i]\frac{x^i}{i!})^k[x^n]=(\sum_{i=0}^n[d|i]e^x)^k [x^n]$$
直接单位根反演，将后式化简为$$(\frac{1}{d}\sum_{i=0}^{d-1}e^{w_d^ix})^k[x^n]$$
当$ d=2$时我们实际要求的就是$$(\frac{e^x+e^{-x}}{2})^k[x^n]$$
直接二项式展开即可
当$ d=3$时用类似的做法三项式展开即可
时间复杂度$ O(k^{d-1}·\log)$
代码
#include<ctime>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#define p 19491001
#define rt register int
#define ll long long
using namespace std;
inline ll read(){
ll x=;char zf=;char ch=getchar();
while(ch!='-'&&!isdigit(ch))ch=getchar();
if(ch=='-')zf=-,ch=getchar();
while(isdigit(ch))x=x*+ch-'',ch=getchar();return x*zf;
}
void write(ll y){if(y<)putchar('-'),y=-y;if(y>)write(y/);putchar(y%+);}
void writeln(const ll y){write(y);putchar('\n');}
int k,m,n,x,y,z,cnt,ans,d;
int inv[],jc[],njc[];
int ksm(int x,int y=p-){
x=(x%p+p)%p;
int ans=;
for(rt i=y;i;i>>=,x=1ll*x*x%p)if(i&)ans=1ll*ans*x%p;
return ans;
}
inline int C(int x,int y){
return 1ll*jc[x]*njc[y]%p*njc[x-y]%p;
}
namespace subtask1{
void main(){
write(ksm(k,n));
return;
}
}
namespace subtask2{
void main(){
int ans=;
for(rt i=;i<=k;i++)(ans+=1ll*C(k,i)*ksm(i+i-k,n)%p)%=p;
ans=1ll*ans*ksm(ksm(,k))%p;
writeln(ans);
return;
}
}
namespace subtask3{
void main(){
int ans=;
int w[];w[]=;w[]=ksm(,(p-)/);w[]=1ll*w[]*w[]%p;
for(rt i=;i<=k;i++)
for(rt j=;i+j<=k;j++){
int xs=(1ll*w[]*i%p+1ll*w[]*j%p+1ll*w[]*(k-i-j)%p)%p;
xs=ksm(xs,n);
(ans+=1ll*C(k,i)*C(k-i,j)%p*xs%p)%=p;
}
ans=1ll*ans*ksm(ksm(,k))%p;
writeln(ans);
return;
}
}
int main(){
cin>>n>>k>>d;
for(rt i=;i<=;i++)jc[i]=njc[i]=inv[i]=;
for(rt i=;i<=k;i++){
jc[i]=1ll*jc[i-]*i%p;
inv[i]=1ll*inv[p%i]*(p-p/i)%p;
njc[i]=1ll*njc[i-]*inv[i]%p;
}
if(d==)subtask1::main();
if(d==)subtask2::main();
if(d==)subtask3::main();
return ;
}