标签：数学
题目
Description
Input
输入仅一行五个正整数n;A1;a;b;c，意义如上所述。
Output
输出仅一行一个正整数，表示sum 对2^32 取模的结果。
Sample Input
2 0 1 5 1
Sample Output
30
HINT
N<=20,A1,a,b,c<2^32
分析
20pts——直接暴力，时间复杂度O(4^n)
正解
玄学地发现类似于FFT中的蝴蝶操作
大概就是改成了这样
\[A_i = A_i \ OR \ A_{i+k}, A_{i+k} = A_i \ AND\ A_{i+k}\]然后就解决了爆空间的问题
code
#include<bits/stdc++.h>
#define ll unsigned int
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
ll x[1<<20],a,b,c,ans,n,w=1,bin;
int main(){
cin>>n>>x[0]>>a>>b>>c;bin=1<<n;
rep(i,1,bin-1)x[i]=x[i-1]*a+b;
for(int k=1;k<bin;k<<=1)
rep(i,0,bin-1){
if(i&k)continue;
ll u=x[i]|x[i+k],v=x[i]&x[i+k];
x[i]=u,x[i+k]=v;
}
rep(i,0,bin-1)ans+=x[i]*w,w*=c;
cout<<ans<<endl;
return 0;
}
