傳送門

---

題解：

設$w$為$k$次單位根，由單位根求和引理和二項式定理，可以將我們需要求的東西轉化為：

$$Ans=\sum _{i=0}^{k?1}(w^i+1{)}^n$$

---

代碼：

#include<iostream> #define ll long long #define re register #define cs constusing std::cerr; using std::cout;cs int mod=998244353; inline int mul(int a,int b){ll r=(ll)a*b;return r>=mod?r%mod:r;} inline int power(int a,int b,int res=1){for(;b;b>>=1,a=mul(a,a))(b&1)&&(res=mul(res,a));return res; } inline void Inc(int &a,int b){(a+=b)>=mod&&(a-=mod);}ll n;int k; int ans;signed main(){ // freopen("sun.in","r",stdin);std::cin>>n>>k;n%=mod-1;int wn=power(3,(mod-1)/k),w=1;for(int re i=0;i<k;++i,w=mul(w,wn))Inc(ans,power(w+1,n));cout<<power(k,mod-2,ans);return 0; }

總結

以上是生活随笔為你收集整理的【LOJ6247】九个太阳（单位根反演）（二项式定理）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。