uoj#450. 【集训队作业2018】复读机（单位根反演）
题面
题解
我的生成函数和单位根反演的芝士都一塌糊涂啊……
(d=1)，答案就是(k^n)（因为这里(k)个复读机互不相同，就是说有标号）
(d=2)，我们考虑复读机的生成函数
[left(sum_{i=0}^infty [2|i]{x^iover i!}
ight)^k[x^n]=left(e^x+e^{-x}over 2
ight)^k[x^n]
]
后面那个可以二项式定理展开
顺便说一下，对于形如(e^{ax})项的第(n)项系数就是把(e)展开之后的第(n)项，即({a^nx^nover n!})，我们把(a^n)加入答案就行了
(d=3)，用单位根反演来化式子
[egin{aligned}
ans
&=left(sum_{i=0}^infty [3|i]{x^iover i!}
ight)^k[x^n]\
&=left({1over 3}sum_{i=0}^infty{x^iover i!}sum_{j=0}^{2}omega_3^{ij}
ight)^k[x^n]\
&=left({1over 3}sum_{i=0}^infty{x^i+(xomega_3^1)^i+(xomega_3^2)^iover i!}
ight)^k[x^n]\
&=left({1over 3}(e^x+e^{xomega_3^1}+e^{xomega_3^2})
ight)^k[x^n]\
end{aligned}
]
因为(3|P-1)，所以单位根就是(omega=g^{P-1over 3})，(P)的原根为(g=7)
//minamoto
#include<bits/stdc++.h>
#define R register
#define ll long long
#define fp(i,a,b) for(R int i=a,I=b+1;i<I;++i)
#define fd(i,a,b) for(R int i=a,I=b-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
using namespace std;
const int N=5e5+5,P=19491001;
inline int add(R int x,R int y){return x+y>=P?x+y-P:x+y;}
inline int dec(R int x,R int y){return x-y<0?x-y+P:x-y;}
inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}
int ksm(R int x,R ll y){
x=(x%P+P)%P;
R int res=1;
for(;y;y>>=1,x=mul(x,x))if(y&1)res=mul(res,x);
return res;
}
int fac[N],ifac[N],w[5],n,k,d,res;
inline int C(R int n,R int m){return m>n?0:1ll*fac[n]*ifac[m]%P*ifac[n-m]%P;}
namespace solve2{
void MAIN(){
res=0;
fp(i,0,k)res=add(res,mul(C(k,i),ksm(2*i-k,n)));
res=mul(res,ksm(2,1ll*k*(P-2)%(P-1)));
printf("%d
",res);
}
}
namespace solve3{
void MAIN(){
res=0;
w[0]=1,w[1]=ksm(7,(P-1)/3),w[2]=mul(w[1],w[1]);
fp(i,0,k)fp(j,0,k-i){
int x=(1ll*i*w[0]%P+1ll*j*w[1]%P+1ll*(k-i-j)*w[2]%P)%P;
x=ksm(x,n);
res=add(res,1ll*C(k,i)*C(k-i,j)%P*x%P);
}
res=mul(res,ksm(3,1ll*k*(P-2)%(P-1)));
printf("%d
",res);
}
}
int main(){
// freopen("testdata.in","r",stdin);
scanf("%d%d%d",&n,&k,&d);
if(d==1)return printf("%d
",ksm(k,n)),0;
else{
fac[0]=ifac[0]=1;fp(i,1,k)fac[i]=mul(fac[i-1],i);
ifac[k]=ksm(fac[k],P-2);fd(i,k-1,1)ifac[i]=mul(ifac[i+1],i+1);
d==2?solve2::MAIN():solve3::MAIN();
}
return 0;
}