题面
题目描述
一个匹配模式是由一些小写字母和问号组成的一个字符串。当一个由小写字母组成的字符串 \(s\)，长度和匹配模式长度相同，并且在对应的每一位都相等或模式串相应位置是问号，则称字符串 \(s\) 与这个模式相匹配。例如：abc与a?c匹配，但不与a?b或abc?相匹配。
现给你 \(n\) 个长度相同的模式串，恰好与其中 \(m\) 个模式串相匹配的字符串有多少个?
输入格式
第一行两个整数，\(n\) 和 \(m\)，含义如题目描述。
接下来 \(n\) 行，每行输入一个只含有小写字母和字符?的字符串，保证所有字符串均等长，表示 \(n\) 个模式串。
输出格式
一个整数，为题目描述中问题的结果 \(\mod 1000003\)。
样例输入1
2 2
a?
?b
样例输出1
1
样例输入2
1 1
?????
样例输出2
881343
说明/提示
\(1 \leq n,m \leq 15\)，字符串长度小于 \(50\)。
题解
看到 \(n,m\) 的范围以及求方案数果断想到状压 dp。
我们设 \(f_{i,s}\) 表示当前匹配到第 \(i\) 位，状态为 \(s\) 的方案数。\(s\) 为一个长度为 \(n\) 的二进制数，记录当前与 \(n\) 个串的匹配状态。
我们再预处理一个 \(g\) 数组，\(g_{i,j}\) 表示在模式串的第 \(i\) 位是字母 \(j\) 时，能匹配的模式串的位置，换句话说，第 \(i\) 位 是 \(j\) 或问号的模式串的位置，仍然可以使用状压存储。
由于有恰好 \(m\) 个匹配的限制，我们倒序处理。
设模式串长为 \(l\)。
我们先对全部匹配完成状态 \(f_{l+1,j}\) 赋初始值，遍历每种可能的 \(j\)，如果 \(j\) 中恰好有 \(m\) 个 \(1\)，那么 \(f_{l+1,j}=1\)，否则 \(f_{l+1,j}=0\)
随后我们从 \(l\) 到 \(1\) 遍历 \(i\)，则显然有转移如下：
\[f_{i,j}=\sum\limits_{k=0}^{25}f_{i+1,j \operatorname{and} g_{i,k}} \]暴力转移即可。复杂度 \(O(l \times 2^n \times 26)\)
code:
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define debug cout<<"DEBUG"<<endl;
#define pb push_back
#define pii pair<int,int>
#define vi vector<int>
#define imp map<int,int>
using namespace std;
const int N=20,M=100,mod=1e6+3;
int n,m,l;
ll g[M][30],f[M][50000];
char c[N][M];
int main(){
freopen("match.in","r",stdin);
freopen("match.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>c[i]+1;
}
l=strlen(c[1]+1);
for(int i=1;i<=l;i++){
for(int j=0;j<26;j++){
g[i][j]=0;
for(int k=1;k<=n;k++){
if(c[k][i]=='?'||c[k][i]==j+'a'){
g[i][j]|=(1<<(k-1));
}
}
}
}
for(int i=l+1;i>0;i--){
for(int j=0;j<(1<<n);j++){
if(i==l+1){
int res=0;
for(int k=1;k<=n;k++){
if(j&(1<<(k-1))){
res++;
}
}
if(res==m){
f[i][j]=1;
}else{
f[i][j]=0;
}
}else{
f[i][j]=0;
for(int k=0;k<26;k++){
f[i][j]+=f[i+1][j&g[i][k]];
f[i][j]%=mod;
}
}
}
}
cout<<f[1][(1<<n)-1]<<endl;
return 0;
}