【题解】SDOI2009Bill的挑战

　　这题好像状压的做法比较的无脑？但想记录一下容斥的做法，感觉自己对于容斥简直一无所知。这道题目容斥的解法我也是看了题解才会的。如有雷同，是我看的(*/ω＼*)我们可以首先枚举当前字符串与给定的哪 (k) 个匹配（给定的范围很小，枚举一下也只要 (2^{n})）。但这样我们求出的是至少与 (k) 个字符串匹配的方案数，因为在保证与这 (k) 个字符串匹配的时候，我们并没有要求说与其他的 (n - k) 个字符串不相匹配。

　　我们令上面求出来的数组叫做 (num[k]) ，现在要求出恰好与 (k) 个串匹配的数组 (ans[k])。一个感觉是 (num[k] = ans[k] + ans[k + 1] + ... + ans[n])，但事实上并不是如此。之前我们只考虑 (k) 个字符串求出来的 (num[k]) 中，有许多重复的方案。例如 (?a) 与 (b?) 的例子，在枚举到第一个字符串的时候，我们会统计 (ba) 一次，而在枚举第二个的时候，我们又会统计到 (ba) 一次。那么 (ans[x]) 究竟在 (num[k]) 中被统计了多少次？应当是 (C(x, k)) 次，因为这枚举的 (k) 个可能是 (x) 个当中的任意 (k) 个。

#include <bits/stdc++.h>
using namespace std;
#define maxn 2000
#define int long long
#define mod 1000003
int n, K, len, num[maxn], ans[maxn], C[maxn][maxn];
string s[maxn], S[maxn];

int read()
{
    int x = 0, k = 1;
    char c; c = getchar();
    while(c < '0' || c > '9') { if(c == '-') k = -1; c = getchar(); }
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * k;
}

void pre()
{
    for(int i = 0; i < maxn; i ++) C[i][0] = 1;
    for(int i = 1; i < maxn; i ++)
        for(int j = 1; j < maxn; j ++)
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
}

int Qpow(int x, int timer)
{
    int base = 1;
    for(; timer; timer >>= 1, x = x * x % mod)
        if(timer & 1) base = base * x % mod;
    return base;
}

void dfs(int now, int tot)
{
    if(now == n + 1)
    {
        int cnt = 0;
        for(int j = 0; j < len; j ++)
        {
            int t = -1;
            for(int i = 1; i <= tot; i ++)
            {
                int x = S[i][j] - 'a'; if(x == -34) x = -1;
                if(t != -1 && (x != -1 && x != t)) return;
                if(t == -1) t = x;
            }
            if(t == -1) cnt ++;
        }
        num[tot] = (num[tot] + Qpow(26, cnt)) % mod;
        return;
    }
    dfs(now + 1, tot);
    S[tot + 1] = s[now]; dfs(now + 1, tot + 1);
}

void init()
{
    memset(ans, 0, sizeof(ans));
    memset(num, 0, sizeof(num));
}

signed main()
{
    int T = read(); pre();
    while(T --)
    {
        n = read(), K = read(); init();
        for(int i = 1; i <= n; i ++) cin >> s[i];
        len = s[1].length();
        dfs(1, 0);
        for(int i = n; i >= K; i --)
        {
            int t = num[i]; 
            for(int j = i + 1; j <= n; j ++)
                t = (t - (C[j][i] * ans[j]) % mod + mod) % mod;
            ans[i] = t;
        }
        printf("%lld
", ans[K]);
    }
    return 0;
}