P2167 [SDOI2009]Bill的挑战
Coros_Trusds
·
·
题解
更好的阅读体验
状压 \rm Dp 小清新题。
题目大意
这次，比赛规则是这样的：
给出 $N$ 个长度相同的字符串（由小写英文字母和 `?` 组成），$S_1,S_2,\dots,S_N$，求与这 $N$ 个串中的刚好 $K$ 个串匹配的字符串 $T$ 的个数，答案对 $1000003$ 取模。
若字符串 $S_x(1\le x\le N)$ 和 $T$ 匹配，满足以下条件：
1. $|S_x|=|T|$。
2. 对于任意的 $1\le i\le|S_x|$，满足 $S_x[i]= \texttt{?}$ 或者 $S_x[i]=T[i]$。
其中 $T$ 只包含小写英文字母。
# 题目分析
令 $dp[i][s]$ 表示所有字符串匹配到第 $i$ 个字符，选择的字符串集合为 $s$ 时匹配的方案数，$g[i][ch]$ 表示在所有字符串的第 $i$ 个字符中字符 $ch$ 出现的状态集合。
初始化 $dp[0][2^n-1]=1$。
那么我们不难求出转移式：$dp[i+1][s\operatorname{and}g[i+1][ch]]\gets dp[i+1][s\operatorname{and}g[i+1][ch]]+dp[i][s]$。
注意 `?` 可以认为是任意一种字符，所以会出现在任意属于字符 $ch$ 的集合内。
# 代码
```cpp
//2022/5/20
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <climits>//need "INT_MAX","INT_MIN"
#include <cstring>//need "memset"
#include <numeric>
#include <algorithm>
#define enter putchar(10)
#define debug(c,que) std::cerr << #c << " = " << c << que
#define cek(c) puts(c)
#define blow(arr,st,ed,w) for(register int i = (st);i <= (ed); ++ i) std::cout << arr[i] << w;
#define speed_up() std::ios::sync_with_stdio(false),std::cin.tie(0),std::cout.tie(0)
#define mst(a,k) memset(a,k,sizeof(a))
#define stop return(0)
const int mod = 1e6 + 3;
inline int MOD(int x) {
if(x < 0) x += mod;
return x % mod;
}
namespace Newstd {
char buf[1 << 21],*p1 = buf,*p2 = buf;
inline int getc() {
return p1 == p2 && (p2 = (p1 = buf) + fread(buf,1,1 << 21,stdin),p1 == p2) ? EOF : *p1 ++;
}
inline int read() {
int ret = 0,f = 0;char ch = getc();
while (!isdigit(ch)) {
if(ch == '-') f = 1;
ch = getc();
}
while (isdigit(ch)) {
ret = (ret << 3) + (ret << 1) + ch - 48;
ch = getc();
}
return f ? -ret : ret;
}
inline void write(int x) {
if(x < 0) {
putchar('-');
x = -x;
}
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
}
using namespace Newstd;
const int N = 55,M = 16;
int g[N][N],dp[N][1 << M];
//dp[i][s]:选择的字符串集合为 s,匹配到第 i 个字符时匹配的方案数
char s[M][N];
int T,n,m;
inline void init() {
mst(dp,0),mst(g,0);
}
inline int getid(char ch) {
return ch - 'a';
}
inline int popcount(int x) {
int res = 0;
while (x) {
if (x & 1) res ++;
x >>= 1;
}
return res;
}
inline void solve() {
scanf("%d%d",&n,&m);
for (register int i = 1;i <= n; ++ i) scanf("%s",s[i] + 1);
int len = strlen(s[1] + 1);
for (register int i = 1;i <= len; ++ i) {
for (register char ch = 'a';ch <= 'z'; ++ ch) {
for (register int j = 1;j <= n; ++ j) {
if (s[j][i] == '?' || s[j][i] == ch) {
g[i][getid(ch)] |= (1 << (j - 1));
}
}
}
}
dp[0][(1 << n) - 1] = 1;
for (register int i = 0;i < len; ++ i) {
for (register int j = 0;j < (1 << n); ++ j) {
if (dp[i][j] == 0) continue;
for (register char ch = 'a';ch <= 'z'; ++ ch) {
dp[i + 1][j & g[i + 1][getid(ch)]] = MOD(dp[i + 1][j & g[i + 1][getid(ch)]] + dp[i][j]);
}
}
}
int ans = 0;
for (register int i = 0;i < (1 << n); ++ i) {
if (popcount(i) == m) {
ans = MOD(ans + dp[len][i]);
}
}
printf("%d\n",ans);
}
int main(void) {
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
scanf("%d",&T);
while (T --) {
init();
solve();
}
return 0;
}
```