CodeChef Cards, bags and coins

tony102

2021 年 01 月 13 日

1813 次浏览

暂无评论

915字数

题解

[Link](https://www.codechef.com/APRIL14/problems/ANUCBC/)

## Description

$n$个数字,选出其一个子集。求有多少子集满足其中数字之和是$m$的倍数。$n ≤ 100000,m ≤ 100$, 最多$90$组数据。

## Sol

暴力的话，是不是跟货币系统那个背包选东西记方案数的那个有点像。但是你发现它范围太大了，但是 $m$ 很小。考虑把物品转化成每一个$a_i \ mod\  m$ 的余数，那么这样的物品只会有 $\leq 100$ 个。我们记 $cnt_k$ 表示 $a_i \equiv k \ (mod\ m)$ 的个数。

设 $g_i$ 表示选出一些物品使得他们模$m$等于$i$的方案数，那么这就等于一些组合数的和。

然后背包转移，转移是$f[i][j] = (f[i][j] + f[i - 1][(j - k + m)\% m] * g[i][k])$

随便背包

## Code

```c++
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int SIZE_N = 1e5 + 5, SIZE_M = 1e2 + 5;
const int mod = 1000000009;

int n, q, m, t;
int g[SIZE_M][SIZE_M], f[SIZE_M][SIZE_M], inv[SIZE_N], fac[SIZE_N], cnt[SIZE_M], a[SIZE_N];

namespace ae86 {
	const int bufl = 1 << 15;
	char buf[bufl], *s = buf, *t = buf;
	inline int fetch() {
		if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
		return *s++;
	}
	inline int read() {
		int a = 0, b = 1, c = fetch();
		while (!isdigit(c))b ^= c == '-', c = fetch();
		while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
		return b ? a : -a;
	}
}
using ae86::read;

int qPow(int a, int b) {
	int ans = 1;
	for ( ; b; b >>= 1, a = a * a % mod) {
		if (b & 1) ans = ans * a % mod;
	}
	return ans;
}

void init() {
	fac[0] = 1; int siz = 1e5;
	for (int i = 1; i <= siz; ++ i) fac[i] = fac[i - 1] * i % mod;
	inv[siz] = qPow(fac[siz], mod - 2);
	for (int i = siz - 1; ~i; -- i) inv[i] = inv[i + 1] * (i + 1) % mod;
}

int C(int x, int y) {
	if (!x) return 0;
	return fac[x] * inv[y] % mod * inv[x - y] % mod;
}

void pre() {
	memset(cnt, 0, sizeof(cnt));
	for (int i = 1; i <= n; ++ i) ++ cnt[(a[i] % m + m) % m];
	for (int i = 0; i < m; ++ i) {
		++ g[i][0]; g[i][i % m] += cnt[i] % mod;
		for (int j = 2; j <= cnt[i]; ++ j) 
			g[i][(i * j) % m] = (g[i][(i * j) % m] + C(cnt[i], j) % mod) % mod;
	}
}

signed main() {
	// freopen("code.in", "r", stdin);
	// freopen("code.out", "w", stdout);
	t = read(); init();
	while (t --) {
		n = read(), q = read();
		for (int i = 1; i <= n; ++ i) a[i] = read();
		while (q --) {
			m = read();
			pre();
			f[0][0] = g[0][0];
			for (int i = 1; i < m; ++ i) { 
				for (int j = 0; j < m; ++ j) {
					for (int k = 0; k < m; ++ k) {
						f[i][j] = (f[i][j] + f[i - 1][(j - k + m) % m] * g[i][k] % mod) % mod;
					}
				}
			}
			printf("%lld\n", f[m - 1][0]);
			memset(f, 0, sizeof(f)); memset(g, 0, sizeof(g));
		}
	}
	return 0;
}
```

最后修改：2021 年 08 月 19 日