2796_幸运值_数论

发布于 2017-10-26  10 次阅读


题目描述

校庆志愿者小Z在休息时间和同学们玩卡牌游戏。一共有n张卡牌,每张卡牌上有一个数Ai,每次可以从中选出k张卡牌。一种选取方案的幸运值为这k张卡牌上数的异或和。小Z想知道所有选取方案的幸运值之和除以998244353的余数。


 

思路

#include 
#include 
#include 
using namespace std;
#define min(x, y) ((x) < (y) ? (x) : (y))
#define N 100010
#define LL long long
const int p = 998244353;
#define M 2000
int t[32];
LL jc[N], ny[N];
inline int read()
{
	int x = 0, p = 1; char ch = getchar();
	while (ch < '0' || ch > '9') {if (ch == '-') p = -1; ch = getchar();}
	while (ch >= '0' && ch <= '9') {x = (x << 1) + (x << 3) + ch - '0'; ch = getchar();}
	return x * p;
}
LL pow(LL x, LL y)
{
	LL b = 1;
	while (y)
	{
		if (y & 1) b = b * x % p;
		y >>= 1;
		x = x * x % p;
	}
	return b;
}
LL c(int m, int n)
{
	if (m < n) return 0;
	return jc[m] * ny[m - n] % p * ny[n] % p;
}
int main()
{
	int n = read(), m = read();
	jc[0] = ny[0] = 1;
	for (int i = 1; i <= n; i++)
	{
		int x;
		x = read();
		for (int j = 0; j <= 30; j++)
			if (x & (1 << j)) t[j]++;
		jc[i] = jc[i - 1] * i % p;
		ny[i] = pow(jc[i], p - 2);
	}
	LL ans = 0;
	for (int j = 0; j <= 30; j++)
	{
		LL tot = 0;
		for (int i = 1; i <= m; i += 2)
		{
			tot += c(t[j], i) * c(n - t[j], m - i) % p;
			tot %= p;
		}
		ans += (1 << j) * tot % p;
		ans %= p;
	}
	printf("%lld\n", ans);
}

  

将每一个数拆为32位二进制,逐位判断,记录一个当前位有多少个1,对于答案有贡献的显然为奇数个1,然后跑组合数即可

 

]]>


「墨泼三千烟火,许你一世迷离」