CodeChef Cards, bags and coins

发布于 9 天前  20 次阅读


Link

Translation

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

#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;
}

学会生存 学会关心