Topcoder8307 SRM390 SetOfPatterns

其实这是一道简单题不知道为什么1AC

定义\(dp[i][S]\)表示前\(i\)的长度，取了\(S\)这个集合，这样就可以用\(dp[i][S]\)更新\(dp[i+1][S与v]​\)。
最后统计一下答案就好了。

代码

#include<bits/stdc++.h>
using namespace std;
const int M=1000003;
int st,cnt,dp[52][1<<15],len,ans,n;//f[x][y]表示到第x位已经考虑了y（二进制表示） 
char c;
class SetOfPatterns{
    public:
        int howMany(vector<string>s,int k){
            n=s.size();
            len=s[0].size();
            for(int i=0;i<len;i++)//考虑每一位 
                for(c='a';c<='z';c++){//考虑这一位上放什么 
                    st=0;//st表示这一位上可以成为c的方案（二进制表示） 
                    for(int j=0;j<n;j++)
                        if(s[j][i]=='?'||s[j][i]==c)st|=1<<j;
                    if(!i)dp[i][st]++;
                    else for(int j=0;j<1<<n;j++)(dp[i][st&j]+=dp[i-1][j])%=M;
                }
            for(int i=0;i<1<<n;i++){
                cnt=0;
                for(int j=0;j<n;j++)
                    if(i&(1<<j))cnt++;
                if(cnt==k)(ans+=dp[len-1][i])%=M;
            }
            return ans;
        }
};