题目描述

输入输出格式

输入格式：

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

输出格式：

如题

输入输出样例

输入样例#1：

53 3???r?????????????????3 4????????????a????????3 3????????a??j??????aa?3 2a????????????????????3 2??????????a???????a??

输出样例#1：

9148520087123467018

说明

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

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

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

 

题解：

　　不知道为什么被我水过了，设dp[i][S]表示当前正在dp第i位，S表示有哪些串已经不合法了（合法为1，不合法为0），转移的话枚举一个字母，然后填上去，判断一下现在有那些串不合法就可以了。

　　状态有50*2^15个，转移是15*26的，这样子都可以水过去，本来想先写一个，优化一下的……

 

代码：

　　

// luogu-judger-enable-o2#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #define RG register#define mod 1000003#define ll long longusing namespace std;char a[100][100];ll dp[52][(1<<17)+1];int n,K,len;int getnum(int S){ int num=0; while(S!=0){ if(S%2==1) num++; S/=2; } return num;}void work(){ cin>>n>>K; for(int i=1;i<=n;i++) scanf("%s",a[i]+1); len=strlen(a[1]+1); memset(dp,0,sizeof(dp)); dp[1][(1<
            
             0;S--){ if(dp[i][S]!=0){ if(getnum(S)
             
              0;S--){ if(getnum(S)==K) ans+=dp[len+1][S],ans%=mod; } printf("%lld\n",ans);}int main(){ int t;cin>>t; while(t--) work(); return 0;}