题目描述
给你\(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_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<cstdio>
#include<cstring>
#include<algorithm>
#include<utility>
#include<iostream>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
void open(const char *s)
{
#ifndef ONLINE_JUDGE
char 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<n;i++)
{
rev[i]=(rev[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<n;j+=i)
{
int w=1;
for(int k=j;k<j+i/2;k++)
{
int u=a[k];
int v=(ll)a[k+i/2]*w%p;
a[k]=(u+v)%p;
a[k+i/2]=(u-v)%p;
w=(ll)w*wn%p;
}
}
}
if(t==-1)
{
ll inv=fp(n,p-2);
for(int i=0;i<n;i++)
a[i]=a[i]*inv%p;
}
}
int main()
{
// freopen("e.in","r",stdin);
scanf("%s",s+1);
int n=0,k;
scanf("%d",&k);
int len=strlen(s+1);
for(int i=1;i<=len;i++)
n=((ll)n*10+s[i]-'0')%p2;
ll w=fp(g,(p-1)/k);
ll now=1;
for(int i=0;i<k;i++)
{
a[i]=fp(now+1,n)%p;
now=now*w%p;
}
ntt(a,k,-1);
ll ans=0;
for(int i=0;i<k;i++)
ans=(ans^((a[i]+p)%p));
printf("%lld\n",ans);
return 0;
}