题解 P2167 【[SDOI2009]Bill的挑战】

· · 题解

一般化的题目描述：

有n个属性，求恰好满足k个属性的物品个数

你有一个函数q(S)，可以快速算出至少满足属性集合S的物品个数（保证每个物品最多只会被统计一次）

设f(S)表示只满足属性集合S中的物品的个数，那么答案就是\sum_{S \subseteq U \wedge |S| = k}f(S)

设f(S)=\sum\limits_{S \subseteq P}q(P)g(|P|)，其中|S|=k，显然有g(x)=(-1)^{x-k}

证明：

对于一个物品t，假设它的属性集合为Q，且S \subseteq Q，且|Q|=k+u

那么它对f(S)的贡献是

\sum_{i=0}^{u}{u \choose i}(-1)^{i}=(-1+1)^{u}=[u=0]

也就是说f(S)=\sum\limits_{S \subseteq P}q(P)(-1)^{|P|-k}

也就是说

\begin{aligned}T&=\sum\limits_{S \subseteq U \wedge |S| = k}f(S) \\&=\sum\limits_{S \subseteq U \wedge |S| = k} \sum_{S \subseteq P}q(P)(-1)^{|P|-k} \\&=\sum\limits_{P \subseteq U \wedge |P| \ge k} q(P)(-1)^{|P|-k}{|P| \choose k}\end{aligned}

于是就做完了……

由于这道题的q(S)求法十分简单，在此就不赘述了

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e6 + 3;
char s[20][55];
int n, k, vis[55], len;
ll pw(ll a, ll b) {
    ll r = 1;
    for( ; b ; b >>= 1, a = a * a % mod) if(b & 1) r = r * a % mod;
    return r;
}
ll calc(int s) {
    for(int i = 1 ; i <= len ; ++ i) {
        vis[i] = 0;
    }
    for(int i = 1 ; i <= n ; ++ i) {
        if((s >> (i - 1)) & 1) {
            for(int j = 1 ; j <= len ; ++ j) {
                char c = :: s[i][j];
                if(c == '?') continue;
                if(vis[j] && vis[j] != c) {
                    return 0;
                }
                vis[j] = c;
            }
        }
    }

    ll res = 1;
    for(int i = 1 ; i <= len ; ++ i) {
        if(vis[i]) continue;
        res = res * 26 % mod;
    }

    return res;
}

int C[20][20];

void sol() {
    scanf("%d%d", &n, &k);
    for(int i = 1 ; i <= n ; ++ i) {
        scanf("%s", s[i] + 1);
    }
    len = strlen(s[1] + 1);
    int ans = 0;
    for(int s = 0 ; s < (1 << n) ; ++ s) {
        int cnt = 0;
        for(int i = 1 ; i <= n ; ++ i) {
            if((s >> (i - 1)) & 1) {
                ++ cnt;
            }
        }
        if(cnt >= k) {
            ll sig = ((cnt - k) & 1) ? -1 : 1;
            ans = (ans + sig * C[cnt][k] * calc(s)) % mod;
        }
    }
    ans = (ans % mod + mod) % mod;
    printf("%d\n", ans);
}

int main() {
    C[0][0] = 1;
    for(int i = 1 ; i < 20 ; ++ i) {
        C[i][0] = 1;
        for(int j = 1 ; j < 20 ; ++ j) {
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
        }
    }
    int T; scanf("%d", &T);
    while(T --) sol(); 
}