CF1034E Little C Loves 3 III

CF1034E Little C Loves 3 III

子集卷积, \(len\le 2^{21},0\le a[i],b[i]\le 3,ans\%4\)

即对于 \(i\in[0,2^n-1]\) 求出

\[(\sum_{j|k=i,j\&k=0}a[j]\times b[k])\mod 4 \]

看到这题 \(5min\) 莽了个子集卷积上去,MLE on 1

哦, \(64MB\) ,那就压位!

写挂了,调了一个下午,终于 调出来了!

然后 TLE on 7

好了,彻底放弃暴力过去的方法

\(\color{black}{\texttt{z}}\color{red}{\texttt{houakngyang}}\) 告诉我可以 \(O(n\log n)\) ,我深深地感到了我的弱小

具体做法是这样的:设 \(cnt_i\) 表示 \(i\) 的二进制中 \(1\) 的个数

令 \(a_i=2^{2*cnt_i}*s_i\) (\(s\) 是输入的字符串)

\(b_i\) 同理

然后,直接FWT把两个东西或起来,乘上 \(\dfrac{1}{2^{2*cnt_i}}\) 输出

为啥这是对的?

\(\color{black}{\texttt{z}}\color{red}{\texttt{houakngyang}}\) 告诉我:考虑当 \(k=i|j\) 时,\(cnt_i+cnt_j\ge cnt_k\) 。

这有啥用啊?

当 \(i\&j\not=0\) 时,\(\dfrac{cnt_i+cnt_j}{2*cnt_k}>0\) ,\(4^{\frac{cnt_i+cnt_j}{2*cnt_k}}\mod 4=0\) ,不产生贡献

否则产生的贡献恰好是题目所求的。

大结论题。。。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double db;
#define rep(i,x,y) for(int i=x,i##end=y;i<=i##end;++i)
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=0;ch=getchar();}
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return f?x:-x;
}
int rdc(){
	char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	return ch-'0';
}
const int N=1<<21;
int n,m;
LL a[N],b[N];
void fwt(LL*a,int op){
	for(int i=1;i<m;i<<=1)
		for(int j=0;j<m;j+=i<<1)
			for(int k=0;k<i;++k)
				a[i+j+k]+=a[j+k]*op;
}
signed main(){
	m=(1<<(n=read()));
	for(int i=0;i<m;++i)a[i]=(1ll<<(__builtin_popcount(i)<<1))*rdc();
	for(int i=0;i<m;++i)b[i]=(1ll<<(__builtin_popcount(i)<<1))*rdc();
	fwt(a,1),fwt(b,1);
	for(int i=0;i<m;++i)a[i]*=b[i];
	fwt(a,-1);
	for(int i=0;i<m;++i)putchar('0'+((a[i]>>(__builtin_popcount(i)<<1))&3));
	puts("");
	return 0;
}
上一篇:3. 贪心思想(todo)


下一篇:557.翻转字符串中的单词 III