今天看了有关组合数学的一些内容。
首先，排列组合的代码为：
LL C(LL n, LL m)
{
LL ans = 1;
for(LL i = n; i > n-m; i--) //也可for(LL i=n-m+1;i<=n;i++)
ans *= i;
for(LL i = 1; i <= m; i++)
ans /= i;
return ans;
}
LL A(LL n, LL m)
{
LL ans = 1;
for(LLi = n; i > n-m; i--) //也可for(LL i=n-m+1;i<=n;i++)
ans *= i;
return ans;
}
一道组合数学+位运算的题，[HDOJ4810]wall painting
题目大意：有一位画家，有n种颜料，给出n种颜料的值。然后在1到n天中，他每天都会选择相应天数的颜料数进行混合，形成新的一种颜料。（所选的颜料的值全部取异或后得到的数即为新颜料的值）然后对应输出每一天有可能合成颜料值的总和。
精简题意：有n个数，从中选k个数，共有C（n，k）种选择，将每种选择出的k个数异或得到的数相加输出。
思路；首先0和1异或是不会影响结果的，只有1和1异或且1的个数是奇数的时候才会对结果产生影响，所以将每个数都转换成二进制，统计每一位上的1的个数，再利用组合数学解决。
代码如下：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<iostream>
#define MOD 1000003//题目要求
using namespace std;
int bit[33];
long long C[1010][1010];
void init()//（数字金字塔）
{
for(inti=0;i<1010;i++)
{
C[i][i]=C[i][0]=1;
}
for(inti=2;i<1010;i++)
{
for(intj=1;j<i;j++)
{
C[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;//%MOD为限制位数
}
}
}
int main()
{
init();
intn,i,j,k;
while(scanf("%d",&n)!=EOF){
memset(bit,0,sizeof(bit));//给bit[33]赋值0
intcnt,num=0;
for(i=0;i<n;i++)//累加求出这n个数每个位置上1的个数
{
scanf("%d",&k);
cnt=0;
while(k)
{
bit[cnt++]+=k&1;
k>>=1;//右移一位前面补零（相当于除以2）
}
num=max(num,cnt);//这n个数的最大位数
}
for(i=1;i<=n;i++)
{
longlong ans=0;
for(j=0;j<num;j++)
{
if(bit[j])//这一位上不全为0
{
for(k=1;k<=i&&k<=bit[j];k+=2)
{
if(n-bit[j]>=i-k)
{
ans=(ans+(((C[bit[j]][k]*C[n-bit[j]][i-k])%MOD)*(1<<j))%MOD)%MOD;/从二进制第j为1的个数为bit[j]中选出i个数,再从剩下的不为1的个数中选k-i个数
}
}
}
}
printf(i==n?"%d\n":"%d",ans);//[?:句式]
}
}
return0;
}
今天一直在搜知识点，位运算中的挺多写法之前没怎么见过，需要继续熟悉。看的题也挺多水题没必要整理，所以今天就写这一个题解吧。
以上~
