Bzoj4183 tree

蝴蝶操作的鬼畜变形


本文总阅读量
Posted by yjjr's blog on March 15, 2018

标签:数学

题目

题目传送门

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;
}
本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr