{"id":384,"date":"2010-09-30T11:03:00","date_gmt":"2010-09-30T03:03:00","guid":{"rendered":"http:\/\/localhost\/?p=384"},"modified":"2010-09-30T11:03:00","modified_gmt":"2010-09-30T03:03:00","slug":"sdoi2009_bill_challenges","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=384","title":{"rendered":"[Sdoi2009]Bill\u7684\u6311\u6218"},"content":{"rendered":"\n

[Sdoi2009]Bill\u7684\u6311\u6218<\/p>\n

Time Limit:4000MS Memory Limit:65536K
Total Submit:33 Accepted:11
Case Time Limit:1000MS<\/p>\n

Description <\/strong><\/p>\n

<\/p>\n

Input <\/strong><\/p>\n

\u672c\u9898\u5305\u542b\u591a\u7ec4\u6570\u636e\u3002
\u7b2c\u4e00\u884c\uff1a\u4e00\u4e2a\u6574\u6570T\uff0c\u8868\u793a\u6570\u636e\u7684\u4e2a\u6570\u3002
\u5bf9\u4e8e\u6bcf\u7ec4\u6570\u636e\uff1a
\u7b2c\u4e00\u884c\uff1a\u4e24\u4e2a\u6574\u6570\uff0cN\u548cK\uff08\u542b\u4e49\u5982\u9898\u76ee\u8868\u8ff0\uff09\u3002
\u63a5\u4e0b\u6765N\u884c\uff1a\u6bcf\u884c\u4e00\u4e2a\u5b57\u7b26\u4e32\u3002<\/p>\n

Output <\/strong><\/p>\n

1
2 1
a?
?b<\/p>\n

Sample Input <\/strong><\/p>\n<\/p>\n

Sample Output <\/strong><\/p>\n<\/p>\n

Source <\/strong><\/p>\n

Day2
\u4fc4\u3002\u3002\u8fd9\u4e2a\u9898\u76ee\u4e5f\u53ea\u8981\u77e5\u9053\u65b9\u6cd5\u5c31\u5f88\u597d\u505a\u4e86\u3002\u3002\u800c\u8fd9\u79cd\u65b9\u6cd5\u5728TC\u4e0a\u51fa\u73b0\u3002\u3002
\u8bbeRet[Set]\u8868\u793a“\u8ddf”Set\u96c6\u5408\u4e2d\u5b57\u7b26\u4e32\u5339\u914d\u7684\u6570\u91cf\u3002\u3002
\u6ce8\u610f\u662f\u8ddf\uff0c\u4e0d\u662f\u521a\u597d\u8ddf\u3002\u3002\u6240\u4ee5\u53ef\u4ee5\u626b\u63cf\u4e00\u8fb9\u641e\u51fa\u6765\u3002\u3002
\u7b97\u51fa\u6240\u6709Ret[Set]
\u518d\u7528Ans[Set]\u8868\u793a\u521a\u597d\u8ddfSet\u96c6\u5408\u4e2d\u5b57\u7b26\u4e32\u5339\u914d\u7684\u6570\u91cf
\u90a3\u4e48Ans[Set]=Ret[Set]-(Ans[a] )(Set \u662fa\u7684\u771f\u5b50\u96c6)..
\u4ece\u5927\u5230\u5c0f\u7b97\u51faAns[Set]\u518d\u7edf\u8ba1\u5c31\u53ef\u4ee5\u4e86T_T\u3002\u3002
Code\uff1a
#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();
    }
}<\/p>\n

\u5bf9\u4e8e30%\u7684\u6570\u636e\uff0cT \u2264 5\uff0cM \u2264 5\uff0c\u5b57\u7b26\u4e32\u957f\u5ea6\u2264 20\uff1b\u5bf9\u4e8e70%\u7684\u6570\u636e\uff0cT \u2264 5\uff0cM \u2264 13\uff0c\u5b57\u7b26\u4e32\u957f\u5ea6\u2264 30\uff1b\u5bf9\u4e8e100%\u7684\u6570\u636e\uff0cT \u2264 5\uff0cM \u2264 15\uff0c\u5b57\u7b26\u4e32\u957f\u5ea6\u2264 50\u300250 <\/p>\n","protected":false},"excerpt":{"rendered":"

[Sdoi2009]Bill\u7684\u6311\u6218 Time Limit:4000MS Memory Limit:65536KTotal Submit:33 Accepted:11 Case Time Limit:1000MS Description Input \u672c\u9898\u5305\u542b\u591a\u7ec4\u6570\u636e\u3002 \u7b2c\u4e00\u884c\uff1a\u4e00\u4e2a\u6574\u6570T\uff0c\u8868\u793a\u6570\u636e\u7684\u4e2a\u6570\u3002 \u5bf9\u4e8e\u6bcf\u7ec4\u6570\u636e\uff1a \u7b2c\u4e00\u884c\uff1a\u4e24\u4e2a\u6574\u6570\uff0cN\u548cK\uff08\u542b\u4e49\u5982\u9898\u76ee\u8868\u8ff0\uff09\u3002 \u63a5\u4e0b\u6765N\u884c\uff1a\u6bcf\u884c\u4e00\u4e2a\u5b57\u7b26\u4e32\u3002 Output 1 2 1 a? ?b Sample Input Sample Output Source Day2\u4fc4\u3002\u3002\u8fd9\u4e2a\u9898\u76ee\u4e5f\u53ea\u8981\u77e5\u9053\u65b9\u6cd5\u5c31\u5f88\u597d\u505a\u4e86\u3002\u3002\u800c\u8fd9\u79cd\u65b9\u6cd5\u5728TC\u4e0a\u51fa\u73b0\u3002\u3002\u8bbeRet[Set]\u8868\u793a“\u8ddf”Set\u96c6\u5408\u4e2d\u5b57\u7b26\u4e32\u5339\u914d\u7684\u6570\u91cf\u3002\u3002\u6ce8\u610f\u662f\u8ddf\uff0c\u4e0d\u662f\u521a\u597d\u8ddf\u3002\u3002\u6240\u4ee5\u53ef\u4ee5\u626b\u63cf\u4e00\u8fb9\u641e\u51fa\u6765\u3002\u3002\u7b97\u51fa\u6240\u6709Ret[Set]\u518d\u7528Ans[Set]\u8868\u793a\u521a\u597d\u8ddfSet\u96c6\u5408\u4e2d\u5b57\u7b26\u4e32\u5339\u914d\u7684\u6570\u91cf\u90a3\u4e48Ans[Set]=Ret[Set]-(Ans[a] )(Set \u662fa\u7684\u771f\u5b50\u96c6)..\u4ece\u5927\u5230\u5c0f\u7b97\u51faAns[Set]\u518d\u7edf\u8ba1\u5c31\u53ef\u4ee5\u4e86T_T\u3002\u3002Code\uff1a#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 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/384"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=384"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/384\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=384"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=384"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=384"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}