当前位置：首页 > news >正文

【SDOI2009】Bill的挑战

news 来源：原创 2024/5/13 1:01:47

Description

　　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只包含小写英文字母。

Input

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

Output

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

Sample Input

3 3

???r???

???????

3 4

???????

?????a?

???????

3 3

???????

?a??j??

????aa?

3 2

a??????

???????

3 2

???????

???a???

????a??

Sample Output

914852

871234

67018

Hint

【数据范围】
　　对于30%的数据，T≤5，M≤5，字符串长度≤20；
　　对于70%的数据，T≤5，M≤13，字符串长度≤30；
　　对于100%的数据，T≤5，M≤15，字符串长度≤50。

比较套路的容斥。我们设g[i]表示至少匹配了i个字符串的子串个数。f[i]表示g[i]的容斥系数。

处理n个字符串，刚好匹配了m的字符串的问题时，我们设 $f[i]=0(0\leqslant i<m),f[m]=1$ 。对于i>m, $f[i]=-\sum _{0\leqslant j <i}f[j]\cdot \binom{i}{j}$

然后就dfs枚举字符串的集合，显然一个集合的答案就是这个集合中的字符串的的交集中的“？”个数。

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<ctime>
#define ll long long
#define mod 1000003

using namespace std;
inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}

int T;
int n,m,len;
char s[16][55];
ll ans,f[20],c[20][20];
ll ksm(ll t,ll x) {
    ll ans=1;
    for(;x;x>>=1,t=t*t%mod)
        if(x&1) ans=ans*t%mod;
    return ans;
}
void dfs(int v,int tot,char t[]) {
    if(v>n) {
        if(tot<m) return ;
        int cnt=0;
        for(int i=1;i<=len;i++) if(t[i]=='?') cnt++;
        ans=(ans+f[tot]*ksm(26,cnt)%mod)%mod;
        return ;
    }
    dfs(v+1,tot,t);
    char tem[55];
    for(int i=1;i<=len;i++) {
        if(t[i]=='?') {
            tem[i]=s[v][i];
        } else if(s[v][i]=='?') tem[i]=t[i];
        else if(s[v][i]!=t[i]) return ;
    }
    dfs(v+1,tot+1,tem);
}
int main() {
    c[0][0]=1;
    for(int i=1;i<=15;i++)
        for(int j=0;j<=i;j++)
            c[i][j]=(!j||j==i)?1:(c[i-1][j-1]+c[i-1][j])%mod;
    T=Get();
    while(T--) {
        n=Get(),m=Get();
        if(n<m) {cout<<0<<"\n";continue ;}
        memset(f,0,sizeof(f));
        f[m]=1;
        for(int i=m+1;i<=n;i++) {
            for(int j=m;j<i;j++) {
                f[i]=(f[i]-f[j]*c[i][j]%mod+mod)%mod;
            }
        }
        for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
        len=strlen(s[1]+1);
        char tem[55];
        for(int i=1;i<=len;i++) tem[i]='?';
        ans=0;
        dfs(1,0,tem);
        cout<<ans<<"\n";
    }
    return 0;
}