SDOI2009 Bill的挑战

发表于 | 分类于

SDOI2009 Bill的挑战

问题描述：

Sheng bill不仅有惊人的心算能力，还可以轻松地完成各种统计。在昨天的比赛中，你凭借优秀的程序与他打成了平局，这导致Sheng bill极度的不满。于是他再次挑战你。这次你可不能输！

这次，比赛规则是这样的：

给N个长度相同的字符串（由小写英文字母和′$
?$′组成），$S1, S2, . . . , SN$，求与这$N$个串中
的刚好$K$个串匹配的字符串T的个数（答案模$1000003$）。
若字符串$Sx（1 ≤ x ≤ N）$和T匹配，满足以下条件：

  1. $Sx.length = T.length$。
  2. 对于任意的$1 ≤ i ≤ Sx.length$，满足$Sx[i] =$′$
    ?$′
    或者$Sx[i] = T[i]$。
    其中T只包含小写英文字母。

输入格式：

本题包含多组数据。
第一行：一个整数$T$，表示数据的个数。
对于每组数据：
第一行：两个整数，$N$和$K$（含义如题目表述）。
接下来$N$行：每行一个字符串。

输出格式：

对于每组数据，输出方案数目（共$T$行）。

样例输入：

1
2 1
a?
?b

样例输出：

50

数据范围：

对于30%的数据，$T ≤ 5$，$N ≤ 5$，字符串长度$≤ 20$；

对于70%的数据，$T ≤ 5$，$N ≤ 13$，字符串长度$≤ 30$；

对于100%的数据，$T ≤ 5$，$N ≤ 15$，字符串长度$≤50$。

题解

看到这道题，首先去想经典的字符串算法，因为有可以随意匹配的字符？，所以KMP做不了，如果用后缀数组，由于最坏情况下字符串的每一个？都要造26个子串，那么对于长度为50的字符串，就要造$26^{50}$个子串，无论是时间还是空间都无法承受，所以便考虑DP解决，这题的状态设计确实不好想，不同于其他字符串DP，本题数据小，所以应该是状压DP，表示集合的哪一维并不是根据单个串来设计，而是根据所有串是否匹配来表示一个集合。

状态设计如下：

$f[i][j]$表示匹配了$i$个字符的字符串集合$j$所拥有的方案数。

状态转移方程

首先设计一个数组$g[][]$

$g[i][j]=x$表示字符$j$可以和$x$集合内的串的第$i$位匹配

$f[匹配长度][集合]=方案数$

$f[0][全满集合]=1$

$f[i][k∩g[i-1][j]]+=f[递推位数i-1][枚举集合k]$

新技能get！

统计集合中选取的元素数量可以用lowbit而不是一位一位去算！

CODE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int P=1e6+3;
int t,n,k,f[60][1<<17],g[60][27],ans;
char s[20][60];
int lowbit(int x)
{
    return x&(-x);
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        memset(f,0,sizeof(f));
        memset(s,0,sizeof(s));
        memset(g,0,sizeof(g));
        ans=0;
        scanf("%d%d",&n,&k);
        int full=(1<<n)-1;
        f[0][full]=1;
        for(int i=0;i<n;i++)
            scanf("%s",s[i]);
        int len=strlen(s[0]);	
        for(int i=0;i<len;i++) 
            for(int p=0;p<26;p++)
            {    
                g[i][p]=0;
                for(int j=0;j<n;j++)
                    if(s[j][i]=='?'||s[j][i]==p+'a')
                        g[i][p]|=(1<<j);
            }
        for(int i=1;i<=len;i++)
            for(int p=0;p<=full;p++)
                if(f[i-1][p])
                    for(int j=0;j<26;j++)
                    {
                        f[i-1][p]%=P;
                        f[i][p&g[i-1][j]]+=f[i-1][p];
                        f[i][p&g[i-1][j]]%=P;
                    }
        for(int p=0;p<=full;p++)
        {
            int tmp=p,cnt=0;
            while(tmp)
            {
                cnt++;
                tmp-=lowbit(tmp);
            }
            if(cnt==k)
                ans=(ans+f[len][p])%P;
        }
        printf("%d\n",ans);
    }
}