[Sdoi2009]Bill的挑战

Time Limit:4000MS Memory Limit:65536K
Total Submit:33 Accepted:11
Case Time Limit:1000MS

Description

Input

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

Output

1
2 1
a?
?b

Sample Input

Sample Output

Source

Day2
俄。。这个题目也只要知道方法就很好做了。。而这种方法在TC上出现。。
设Ret[Set]表示“跟”Set集合中字符串匹配的数量。。
注意是跟，不是刚好跟。。所以可以扫描一边搞出来。。
算出所有Ret[Set]
再用Ans[Set]表示刚好跟Set集合中字符串匹配的数量
那么Ans[Set]=Ret[Set]-(Ans[a] )(Set 是a的真子集)..
从大到小算出Ans[Set]再统计就可以了T_T。。
Code：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<string>
#include<cstring>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
#define All(x) x.begin(),x.end()
using namespace std;
const int maxn=15,maxL=50,mod=1000003;
int T,N,K;
string A[maxn];
bool C[maxn];
int Ret[1<<maxn];
void Calc_Ret()
{
    static char Fixed[maxL];
    memset(Fixed,0,sizeof Fixed);
    int Set=0;
    int ret=1;
    rep(i,N)if(C[i])
    {
        Set|=1<<i;
        rep(j,A[i].size())
        if(A[i][j]!=’?’)
        {
            if(Fixed[j]&&A[i][j]!=Fixed[j])
            {
                ret=0;
            }
            else
            {
                Fixed[j]=A[i][j];
            }
        }
    }
    rep(j,A[0].size())if(!Fixed[j])ret*=26,ret%=mod;
    Ret[Set]=ret;
}
void Generate_Ways(int str)
{
    if(str==N)
    {
        Calc_Ret();
        return;
    }
    //D choose A[str]
    C[str]=false;
    Generate_Ways(str+1);
    //choose A[str];
    C[str]=true;
    Generate_Ways(str+1);
}
void Calc_Ans()
{
    int Ans=0;
    for(int i=(1<<N)-1;i>=0;i–)
    {
        for(int subset=(i-1)&i;subset>0;subset=(subset-1)&i)
            Ret[subset]=(Ret[subset]-Ret[i]+mod)%mod;
        if(i)Ret[0]=(Ret[0]-Ret[i]+mod)%mod;
    }
    rep(i,(1<<N))
    {
        int cnt=0;
        rep(j,N)if(i>>j&1)cnt++;
        if(cnt==K)Ans+=Ret[i],Ans%=mod;
    }
    cout<<Ans<<endl;
}
void Input_Data()
{
    cin>>N>>K;
    rep(i,N)cin>>A[i];
}
int main()
{
    //freopen("in","r",stdin);
    cin>>T;
    rep(i,T)
    {
        Input_Data();
        Generate_Ways(0);
        Calc_Ans();
    }
}

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