HDU 4810 Wall Painting(异或 +按位容斥)
发布时间：2020-12-13 20:22:36 所属栏目：PHP教程 来源：网络整理
导读：直接不会，预估时间复杂度，对C（n,m） 到范围为500就瞎了。当时也想算法应当接近常数级别的。 如果真的算必定跪。回头看了下解题报告。 话说比赛很喜欢考异或，“位”思想，组合问题 对计算选取k个数字时候，分别计算各个位上可能出现的情况，然后计算各个
|
直接不会，预估时间复杂度，对C（n,m） 到范围为500就瞎了。当时也想算法应当接近常数级别的。 如果真的算必定跪。回头看了下解题报告。 话说比赛很喜欢考异或，“位”思想，组合问题 对计算选取k个数字时候，分别计算各个位上可能出现的情况，然后计算各个位上的累加和。即使1个数字可由很多位组成但是每次计算1个位 记录每位上１的个数（这里只需要３２位），对第i天，必须要选出奇数个１才能使该位异或结果位１，否则为０。我们来看样例， 注意细节：1.预处理C数组，注意范围，1个位上种类的选取是奇数但不能超过可选的数字。特别容易溢出。都用 long long #include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define inf 0x3f3f3f3f
#define maxn 1100
#define MOD 1000003
using namespace std;
int N;
long long rem[32],c[maxn][maxn];
void init() {
c[0][0] = c[1][0] = c[1][1] = 1;
for (int i = 2; i < maxn; i++) {
c[i][0] = 1;
for (int j = 1; j <= i; j++)
c[i][j] = (c[i⑴][j] + c[i⑴][j⑴]) % MOD;
}
return ;
}
int main()
{init();
while(~scanf("%d",&N)){
memset(rem,sizeof(rem));
for(int i=0;i<N;i++){
int k;scanf("%d",&k);
for(int j=0;j<32;j++)
if( (1<<j)& k ) rem[j]++;
}
for(int i=1;i<=N;i++){
long long ans=0;
for(int j=0;j<32;j++){
for(int k=1;k<=rem[j] && k<=i;k+=2)
ans=(ans+ ( c[N-rem[j]][i-k]* (c[rem[j]][k]* ( (1<<j)%MOD) )%MOD)%MOD)%MOD;
}
if(i==N) printf("%I64d
",ans);
else printf("%I64d ",ans);
}
}
return 0;
} （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |