白兔的刁难 IDFT
题目描述
给你\(n,k\)，求
\[ \forall 0\leq t< k,s_t=\sum_{i=-t}^{n-t}[k|i]\binom{n}{i+t} \]
对\(998244353\)取模。
\(k=2^m,m\leq 20,n\leq {10}^{{10}^6}\)
题解
\[ \begin{align} s_t&=\sum_{i=-t}^{n-t}[k|i]\binom{n}{i+t}\\ &=\sum_{i=-t}^{n-t}[i~\bmod k=0]\binom{n}{i+t}\\ &=\sum_{i=-t}^{n-t}\frac{1}{k}\sum_{j=0}^{k-1}{(w_k^i)}^j\binom{n}{i+t}\\ &=\frac{1}{k}\sum_{i=-t}^{n-t}\sum_{j=0}^{k-1}{(w_k^{-t})}^j{(w_k^{i+t})}^j\binom{n}{i+t}\\ &=\frac{1}{k}\sum_{j=0}^{k-1}{(w_k^{-t})}^j\sum_{i=-t}^{n-t}{(w_k^{i+t})}^j\binom{n}{i+t}\\ &=\frac{1}{k}\sum_{j=0}^{k-1}{(w_k^{-t})}^j\sum_{i=0}^{n}{(w_k^i)}^j\binom{n}{i}\\ &=\frac{1}{k}\sum_{j=0}^{k-1}{(w_k^{-t})}^j{(w_k^j+1)}^n\\ &=\frac{1}{k}\sum_{j=0}^{k-1}{(w_k^t)}^{-j}{(w_k^j+1)}^n\\ \end{align} \]
\[ s_i=\frac{1}{k}\sum_{j=0}^{k-1}{(w_k^i)}^{-j}{(w_k^j+1)}^n\\ \]
然后就能发现这是一个IDFT的形式。
直接IDFT就好了。
时间复杂度：\(O(k\log k)\)
代码
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
typedef pair pii;
void open(const char *s)
{
#ifndef ONLINE_JUDGEchar str[100];sprintf(str,"%s.in",s);freopen(str,"r",stdin);sprintf(str,"%s.out",s);freopen(str,"w",stdout);
#endif
}
const ll p=998244353;
const ll p2=998244352;
const ll g=3;
ll fp(ll a,ll b)
{ll s=1;for(;b;b>>=1,a=a*a%p)if(b&1)s=s*a%p;return s;
}
char s[1000010];
int a[2000010];
int rev[2000010];
void ntt(int *a,int n,int t)
{for(int i=1;i>1]>>1)|(i&1?n>>1:0);if(i>rev[i])swap(a[i],a[rev[i]]);}for(int i=2;i<=n;i<<=1){int wn=fp(g,(p-1)/i);if(t==-1)wn=fp(wn,p-2);for(int j=0;j 转载于:https://www.cnblogs.com/ywwyww/p/8538650.html
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！