首页 > 代码库 > HDU 4810 Wall Painting(异或 +按位容斥)
HDU 4810 Wall Painting(异或 +按位容斥)
直接不会,预估时间复杂度,对于C(n,m) 到规模为500就瞎了。当时也想算法应该接近常数级别的。
如果真的算必然跪。回头看了下解题报告。
话说比赛很喜欢考异或,“位”思想,组合问题
对于计算选取k个数字时候,分别计算各个位上可能出现的情况,然后计算各个位上的累加和。即便一个数字可由很多位组成但是每次计算一个位
记录每一位上1的个数(这里只需要32位),对于第i天,必须要选出奇数个1才能使该位异或结果位1,否则为0。我们来看样例,
4
1 2 10 1
这4个数的二进制表示分别为:
0001
0010
1010
0001
比如第2天的时候, 从4个中选出2个来做异或,第4位上只有1个1,所以有3中选法可以使得这一位异或之后结果为1,(也就是C(3,1) * C(1,1)),第3位的没有1,所以异或结果一定为0,第2位上又2个1,所以有4种选法,同理第一位上也是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数组,注意范围,一个位上种类的选取是奇数但不能超过可选的数字。特别容易溢出。都用 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-1][j] + c[i-1][j-1]) % 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\n",ans); else printf("%I64d ",ans); } } return 0; }
HDU 4810 Wall Painting(异或 +按位容斥)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。