【CF453D】 Little Pony and Elements of Harmony（FWT）

喜欢ヅ旅行 2022-01-12 09:37 124阅读 0赞

## 题面 ##

[传送门][Link 1]

设\\(a\\)的递推公式为

\\\[a\_i=\\sum\_ja\_jb\[count(i\\oplus j)\]\\\]

其中\\(\\oplus\\)为异或，\\(count(i)\\)表示\\(i\\)的二进制中\\(1\\)的个数

给出\\(a\_0,b\\)，求\\(a\_t\\)，\\(t\\leq 10^\{18\}\\)

## 题解 ##

如果我们定义\\(c\_i=b\[count(i)\]\\)

这显然就是个异或卷积了……因为要卷\\(t\\)次，所以点值表示乘起来的时候要把\\(c\_i\\)快速幂一下

然而有个尴尬的问题就是这里的模数可能是偶数……那么我们\\(IDFT\\)的时候\\(2\\)显然没有逆元啊……

解决方法是把模数乘上\\(lim\\)（即\\(fwt\\)的数组长度），那么最后\\(IDFT\\)之后把所有数对\\(lim\\)下去整就行了

记得得用快速乘

//minamoto #include<bits/stdc++.h> #define R register #define ll long long #define dd long double #define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i) #define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i) #define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v) using namespace std; char buf[1<<21],*p1=buf,*p2=buf; inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;} int read(){ R int res,f=1;R char ch; while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1); for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0'); return res*f; } ll readll(){ R ll res,f=1;R char ch; while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1); for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0'); return res*f; } const int N=(1<<20)+5; ll P; inline ll add(R ll x,R ll y){return x+y>=P?x+y-P:x+y;} inline ll dec(R ll x,R ll y){return x-y<0?x-y+P:x-y;} inline ll mul(R ll x,R ll y){return x*y-(ll)((dd)x/P*y)*P;} inline ll ksm(R ll x,R ll y){ ll res=1; for(;y;y>>=1,x=mul(x,x))y&1?res=mul(res,x):0; return res; } void Fwt(ll *A,int lim,int ty){ ll t; for(R int mid=1;mid<lim;mid<<=1) for(R int j=0;j<lim;j+=(mid<<1)) fp(k,0,mid-1) A[j+k+mid]=dec(A[j+k],t=A[j+k+mid]), A[j+k]=add(A[j+k],t); if(!ty)fp(i,0,lim-1)A[i]/=lim; } int n,lim;ll t,a[N],c[N],sz[N],b[25]; int main(){ n=read(),t=readll(),P=read(),lim=(1<<n),P*=lim; fp(i,0,lim-1)a[i]=read()%P;fp(i,0,n)b[i]=read()%P; fp(i,0,lim-1)c[i]=b[sz[i]=sz[i>>1]+(i&1)]; Fwt(a,lim,1),Fwt(c,lim,1); fp(i,0,lim-1)a[i]=mul(a[i],ksm(c[i],t)); Fwt(a,lim,0); fp(i,0,lim-1)printf("%I64d\n",a[i]); return 0; }

转载于:https://www.cnblogs.com/bztMinamoto/p/10585756.html

[Link 1]: http://codeforces.com/contest/453/problem/D