[SDOI2009] Bill的挑战
目录题目描述
Sheng_bill 不仅有惊人的心算能力，还可以轻松地完成各种统计。在昨天的比赛中，你凭借优秀的程序与他打成了平局，这导致 Sheng_bill 极度的不满。于是他再次挑战你。这次你可不能输。
这次，比赛规则是这样的：
给出 \(N\) 个长度相同的字符串（由小写英文字母和 ? 组成），\(S_1,S_2,\dots,S_N\)，求与这 \(N\) 个串中的刚好 \(K\) 个串匹配的字符串 \(T\) 的个数，答案对 \(1000003\) 取模。
若字符串 \(S_x(1\le x\le N)\) 和 \(T\) 匹配，满足以下条件：
- \(|S_x|=|T|\)。
- 对于任意的 \(1\le i\le|S_x|\)，满足 \(S_x[i]= \texttt{?}\) 或者 \(S_x[i]=T[i]\)。
其中 \(T\) 只包含小写英文字母。
输入格式
本题包含多组数据。
第一行一个整数 \(T\)，表示数据组数。
对于每组数据，第一行两个整数，\(N\) 和 \(K\)。
接下来 \(N\) 行，每行一个字符串 \(S_i\)。
输出格式
每组数据输出一行一个整数，表示答案。
样例 #1
样例输入 #1
5
3 3
???r???
???????
???????
3 4
???????
?????a?
???????
3 3
???????
?a??j??
????aa?
3 2
a??????
???????
???????
3 2
???????
???a???
????a??
样例输出 #1
914852
0
0
871234
67018
提示
数据规模与约定
- 对于 \(30\%\) 的数据，\(N\le5\)，\(|S_i|\le20\)；
- 对于 \(70\%\) 的数据，\(N\le13\)，\(|S_i|\le30\)；
- 对于 \(100\%\) 的数据，\(1\le T\le 5\)，\(1\le N \le15\)，\(1\le|S_i|\le50\)。
题意概括
我去真不是我说，这个题我真没看懂它到底让我干啥。
后来去看\(OJ\)上的题面，才知道那个长得跟绝对值一样的符号是长度的意思…………
总之是这样的：
给你\(N\)个字符串、你可以从这些字符串里挑选\(K\)个，对这\(K\)个字符串配对出字符串\(T\)，配对规则倒是比较简单：
-
\(K\)个字符串长度和\(T\)相同。
-
对于\(K\)个字符串，每一位必须是'\(?\)'或者与字符串\(T\)的对应位置相同。
也就是说，如果选出的\(K\)个字符串上某一位上都是'\(?\)'，那么这一位可以选择\(26\)个字母。
如果选出的\(K\)个字符串上某一位不是'\(?\)'，那么这一位可以选择这一种字母。
如果选出的\(K\)个字符串某两位不是'\(?\)'且各不相同，那么这一位的选择为\(0\)，整个字符串\(T\)的选择为0。
思路历程
私货：†升天††升天†。
1.设计转移
上来就设计转移！上来就设计转移！
我们就是选嘛，去选一个字符串\(T\)，\(f_{i}\)表示第\(0\)~\(i\)位置有多少种方案嘛，那显然\(1<=i<=50,'a'<=j<='z'\)嘛。
那么我们的转移大抵是这样的：
\[\begin{aligned} f_{i}=max(f_{i},f_{i-1}+第i位置所有可能) \end{aligned} \]然后我们查询最后的\(f_n\)就结束了嘛。
预处理一下第\(i\)位置的方案数就好了嘛。
2.有没有发现少了个\(K\)
刚刚的只适用于\(N==K\)。
显然只适合骗分（
最初呢，我想的是没有关系嘛，我们可以枚举每一个方案~
然而仔细一想，一方面我不会枚举，另一方面万一咱选的\(T\)里面有重的也没办法去掉。（而且这和状态压缩有半毛钱关系）
那我们肯定要更改我们的转移了。
先设计状态，这个设计的状态要满足我们的关键问题：处理\(K\).
我们每一个位置设计一个状态\(ms_{i,j}\)，表示选出的字符串\(T\)的第\(i\)位置如果是字符\(j\)，可以和哪些字符串配对。
例如：
ms[0][a]=3;
//第0位的字符为a,状态为0 1 1,表示可以与第一个和第二个字符串配对。
那么，对于这个\(ms\)数组的初始化是这样的：
ms初始化
/*
变量声明:
len是字符串的长度,都一样长
S存的是字符串,S[k][i]表示第k个字符串的第i位置
*/
for(int i=0;i<len;++i){
for(char j='a';j<='z';++j){
for(int k=1;k<=n;++k){
if(S[k][i]=='?' || S[k][i]==j){
ms[i][j-'a']|=(1<<(k-1));
}
}
}
}
有了这个，我们选状态就可以了呀，\(f_{i,j}\)表示\(0-i\)位置第\(i\)位置的状态是\(j\)时的方案数。
就有转移：
\[\begin{aligned} f_{i+1,ms_{i,ch} 与 j}+=f_{i,j} \end{aligned} \]为什么是加？因为我们这个\(j\)是枚举的状态，所有状态都会加进下一位与他有重叠的状态里。
因为是不断往下走状态中的\(1\)越走越少，因此显然有初始化：
\(f_{0,(1<<n)-1}=1\)
最后我们找答案肯定是从状态中\(1\)的个数等于\(K\)的里面找。
代码实现
Miku's Code
#include<bits/stdc++.h>
using namespace std;
typedef long long intx;
const int maxn=16,maxS=55,maxs=1<<15,mod=1000003;
int T,n,k,len;
char S[maxS][maxS];
int f[maxS][maxs],ms[maxS][27];
inline void input(){
memset(f,0,sizeof(f));
memset(ms,0,sizeof(ms));
scanf("%d %d",&n,&k);
for(int i=1;i<=n;++i){
scanf("%s",S[i]);
}
len=strlen(S[1]);
for(int i=0;i<len;++i){
for(char j='a';j<='z';++j){
for(int k=1;k<=n;++k){
if(S[k][i]=='?' || S[k][i]==j){
ms[i][j-'a']|=(1<<(k-1));
}
}
}
}
}
inline void work(){
f[0][(1<<n)-1]=1;
for(int i=0;i<len;++i){
for(int j=0;j<=(1<<n)-1;++j){
if(f[i][j]){
for(char ch='a';ch<='z';++ch){
f[i+1][ms[i][ch-'a']&j]+=f[i][j];
f[i+1][ms[i][ch-'a']&j]%=mod;
}
}
}
}
}
inline int lowbit(int x){
return x&(-x);
}
inline int count_(int s){
int cnt=0;
while(s){
s=s-lowbit(s);
++cnt;
}
return cnt;
}
int answer(){
int ans=0;
for(int i=0;i<=(1<<n)-1;++i){
if(count_(i)==k) ans=(ans+f[len][i])%mod;
//因为work()中枚举的i到len-1,转移到len,所以是len
}
return ans;
}
int main(){
scanf("%d",&T);
for(int i=1;i<=T;++i){
input();
work();
printf("%d\n",answer());
}
return 0;
}