51 NOD 1406 and query

我们知道一个数S会对所有它的子集S'产生1的贡献，但是我们直接枚举子集是 3^(log2 1000000)的，会炸掉；如果直接把每个有1的位变成0往下推也会凉掉，因为这样会有很多重复的。

但是我们发现第二种方法其实算的是有序的路径方案数，我们尝试把它变成无序的，贡献就正好是1了。

具体的说，我们在外层枚举位数，内层把所有这一位是1的数给把它这一位变成0的数贡献，这样就是无序的了。

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int maxn=1000000;

int n,f[maxn*2+5],ci[35];

inline int read(){

	int x=0; char ch=getchar();

	for(;!isdigit(ch);ch=getchar());

	for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';

	return x;

}

void W(int a){ if(a>=10) W(a/10); putchar(a%10+'0');}  

inline void dp(){

	for(int i=0;i<20;i++)

	    for(int j=maxn;j;j--) if(j&ci[i]) f[j^ci[i]]+=f[j];

}

inline void output(){

	for(int i=0;i<=maxn;i++) W(f[i]),puts("");

}

int main(){

	ci[0]=1;

	for(int i=1;i<=20;i++) ci[i]=ci[i-1]<<1;

	n=read();

	for(int i=1;i<=n;i++) f[read()]++;

	dp();

	output();

	return 0;

}

巴特西

51 NOD 1406 and query

最新文章

热门文章