【SDOI2009】Bill的挑战-白红宇

【SDOI2009】Bill的挑战

阅读量：5891 次

发布时间：2019-06-19

本文共 1565 字，大约阅读时间需要 5 分钟。

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
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #define ll long long#define mod 1000003using 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

转载于:https://www.cnblogs.com/hchhch233/p/9735808.html

你可能感兴趣的文章