[bzoj 1879] [Sdoi2009]Bill的挑战：状压DP，自创数学公式（?）_综合

题意：给N个（1<=N<=15）含小写字母、?的长度不超过50的等长字符串，求有多少个含小写字母的字符串和恰好K个串匹配。?可匹配任意字符。

把它想简单一点就是一道状压DP。

看到“恰好”，我的想法是用能匹配K个串的数目减去能匹配(K+1)个串的数目，定义f[i][j]为和集合j中字符串匹配的字符串数目。因为没想到预处理……

我想用容斥原理，然后走上了推导数学公式（手动打表找规律）的不归路，方法是用容斥原理暴力地展开，用对称性简化计算。

现在，我们问题是：用交集的元素数目表示在n个集合中出现k次的元素数目/恰在n个集合出现k次的元素数目。

前者没有发现明显的规律，计算后者各个项的系数时出现了正整数、三角形数的前几项。画出Pascal三角形，归纳出以下公式：

| ? 1 \leq j 1 < j 2 < ? < j i \leq n A j 1 \cap A j 2 \cap ? \cap A j k | = \sum i = k n (? 1) i ? k C k i \sum 1 \leq j 1 < j 2 < ? < j i \leq n | A j 1 \cap A j 2 \cap ? \cap A j i |

$|\bigcup_{1 \le j_1 \lt j_2 \lt \cdots \lt j_i \le n} A_{j_1} \cap A_{j_2} \cap \cdots \cap A_{j_k}| = \sum_{i=k}^n(-1)^{i-k}C_i^k\sum_{1 \le j_1 \lt j_2 \lt \cdots \lt j_i \le n} |A_{j_1} \cap A_{j_2} \cap \cdots \cap A_{j_i}|$

然后莫名地AC了……

时间复杂度 $O(L2^n)$ 。

先留个坑，有空来证。

#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
const int MAX_N = 15, MAX_L = 50, M = 1000003;
char s[MAX_N][MAX_L+2], g[MAX_L+1][1<<MAX_N];
int N, K, f[MAX_L+1][1<<MAX_N], C[MAX_N+1][MAX_N+1], t[MAX_N+1];template<typename T>
inline int count(T x)
{const static int c[] = {
   0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4};int ans = 0;for (int i = 0; i < sizeof(T)*2; ++i, x >>= 4)ans += c[x & 0xf];return ans;
}inline int log2(int x)
{int r = 0;const static int mask[] = {
   0xff00, 0xf0, 0xc, 0x2};for (int i = 0, a = 8; i < 4; ++i, a >>= 1)if (x & mask[i]) {r += a;x >>= a;}return r;
}int solve()
{int l = strlen(s[0]+1);for (int i = 1; i <= l; ++i)for (int j = 1; j < (1<<N); ++j) {int b = j & -j, x = j ^ b, k = log2(b);if (!g[i][x]) {f[i][j] = g[i][j] = 0;continue;}char c = s[k][i];if (g[i][x] == '?')g[i][j] = c;else if (c == '?')g[i][j] = g[i][x];else if (g[i][x] != c) {f[i][j] = g[i][j] = 0;continue;} elseg[i][j] = c;if (g[i][j] == '?')f[i][j] = f[i-1][j]*26%M;elsef[i][j] = f[i-1][j];}memset(t, 0, sizeof(t));for (int i = 1; i < (1<<N); ++i)t[count(i)] += f[l][i];int r = 0;for (int i = K, sgn = 1; i <= N; ++i, sgn *= -1)(r += (ll) sgn * C[i][K] * t[i] % M + M) %= M;return r;
}int main()
{for (int i = 0; i < (1<<MAX_N); ++i)f[0][i] = 1;for (int i = 1; i <= MAX_L; ++i)g[i][0] = '?';for (int i = 1; i <= MAX_N; ++i) {C[i][0] = C[i][i] = 1;for (int j = 1; j < i; ++j)C[i][j] = (C[i-1][j-1] + C[i-1][j]) % M;}int T;scanf("%d", &T);while (T--) {scanf("%d %d", &N, &K);for (int i = 0; i < N; ++i)scanf("%s", s[i]+1);printf("%d\n", solve());}return 0;
}