nb题
(d=1) 答案是(k^n)
(d=2) 就是求
[n^k
]
可以用二项式定理展开 复杂度(O(klog n))
(d=3) 还是求一个复读机的EGF
[F(x)=sum_i[3|i]frac{x^i}{i!}
]
[=frac{1}{3}sum_ifrac{x^i}{i!}sum_{j=0}^2 w_3^{ij}
]
[=frac{1}{3}(e^x+e^{xw_3^1}+e^{xw_3^2})
]
两次二项式定理 复杂度(O(k^2log n))
#include<bits/stdc++.h>
using namespace std;
#define fp(i,l,r) for(register int (i)=(l);i<=(r);++(i))
#define fd(i,l,r) for(register int (i)=(l);i>=(r);--(i))
#define fe(i,u) for(register int (i)=front[(u)];(i);(i)=e[(i)].next)
#define mem(a) memset((a),0,sizeof (a))
#define O(x) cerr<<#x<<':'<<x<<endl
#define int long long
inline int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return x*f;
}
void wr(int x){
if(x<0)putchar('-'),x=-x;
if(x>=10)wr(x/10);
putchar('0'+x%10);
}
const int mod=19491001;
inline void tmod(int &x){x%=mod;}
inline int qpow(int a,int b){
int res=1;a%=mod;
for(;b;b>>=1,tmod(a*=a))
if(b&1)tmod(res*=a);
return res;
}
inline int ginv(int x){return qpow(x,mod-2);}
int fac[500010],ifac[500010],n,K,d;
inline int C(int n,int m){return fac[n]*ifac[m]%mod*ifac[n-m]%mod;}
inline void solve1(){
printf("%lld
",qpow(K,n));
}
inline void solve2(){
int ans=0;
fp(i,0,K)tmod(ans+=qpow(i+i-K+mod,n)*C(K,i));
printf("%lld
",ans*ginv(qpow(2,K))%mod);
}
inline void solve3(){
int ans=0,w1=qpow(7,(mod-1)/3),w2=w1*w1%mod;
fp(i,0,K)fp(j,0,i){
int t=j*w1+(i-j)*w2+K-i;
tmod(ans+=C(K,i)*C(i,j)%mod*qpow(t,n));
}
printf("%lld
",ans*ginv(qpow(3,K))%mod);
}
main(){
fac[0]=1;fp(i,1,500001)fac[i]=fac[i-1]*i%mod;
ifac[500001]=ginv(fac[500001]);fd(i,500000,0)ifac[i]=ifac[i+1]*(i+1)%mod;
n=read();K=read();d=read();
if(d==1)solve1();
else if(d==2)solve2();
else solve3();
return 0;
}