标签：数学

题目

题目传送门

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中的蝴蝶操作

大概就是改成了这样

Ai=Ai OR Ai+k,Ai+k=Ai AND Ai+k A i = A i   O R   A i + k , A i + k = A i   A N D   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; }