题目
[large {sum_{i=0}^n[k|i]C(n,i)}pmod {998244353}
]
其中(nleq 10^{18}),(k=2^p,pin [0,20])
分析
主要是(k)条件比较难想，但是貌似有点像NTT的原根，
而且这个组合数也难求，二项式定理是一个将组合数转换为一个快速幂的定理
主要是没写过单位根反演，直接推式子算了
单位根有一个很重要的性质就是
[large[n|k]=frac{1}{n}sum_{i=0}^{n-1}omega^{ik}_n
]
然后这个式子就可以写成
[large=frac{1}{k}sum_{i=0}^nsum_{j=0}^{k-1}omega^{ij}_kC(n,i)
]
考虑把有关(i)的部分丢进里面，那就是
[large=frac{1}{k}sum_{j=0}^{k-1}sum_{i=0}^n(omega^j_k)^{i}C(n,i)
]
观察到后面直接套用二项式定理就是
[large=frac{1}{k}sum_{j=0}^{k-1}(omega^j_k+1)^n
]
直接(O(klog_2n))求就可以了
代码
#include <cstdio>
#define rr register
using namespace std;
typedef long long lll;
const lll mod=998244353;
lll n,k,omega,ans;
inline lll ksm(lll x,lll y){
rr lll ans=1;
for (;y;y>>=1,x=x*x%mod)
if (y&1) ans=ans*x%mod;
return ans;
}
signed main(){
scanf("%lld%lld",&n,&k);
omega=ksm(3,(mod-1)/k);
for (rr lll i=0,t=1;i<k;++i)
ans+=ksm(t+1,n),t=t*omega%mod;
return !printf("%lld",ans%mod*ksm(k,mod-2)%mod);
}