HDU 4810 Wall Painting(异或 +按位容斥)

直接不会,预估时间复杂度,对C(n,m) 到范围为500就瞎了。当时也想算法应当接近常数级别的。

如果真的算必定跪。回头看了下解题报告。 

话说比赛很喜欢考异或,“位”思想,组合问题

对计算选取k个数字时候,分别计算各个位上可能出现的情况,然后计算各个位上的累加和。即使1个数字可由很多位组成但是每次计算1个位

记录每位上1的个数(这里只需要32位),对第i天,必须要选出奇数个1才能使该位异或结果位1,否则为0。我们来看样例,

1 2 10 1
这4个数的2进制表示分别为:
0001
0010
1010
0001
比如第2天的时候, 从4个当选出2个来做异或,第4位上只有1个1,所以有3当选法可使得这1位异或以后结果为1,(也就是C(3,1) * C(1,1)),第3位的没有1,所以异或结果1定为0,第2位上又2个1,所以有4种选法,同理第1位上也是4种。
所以其结果就是 (1<<3)*C(3,1) + 0 * C(4,2) + (1<<1)*C(2,1)*C(2,1) + (1<<0)*C(2,1)*C(2,1)

注意细节: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,0,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;
}

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » HDU 4810 Wall Painting(异或 +按位容斥)

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡