记录编号	354143	评测结果	AAAAA
题目名称	[CCPC2015][HDU5548] 麻将 Mahjong	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	5.981 s
提交时间	2016-11-20 00:11:37	内存使用	35.81 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
using namespace std;
const int SIZEN=210;
const int MOD=1000000000+7;
int get(int s,int k){
    return (s>>k)&1;
}
int change(int s,int k,int t){
    s&=(~(1<<k));
    s|=(t<<k);
    return s;
}
void printdig(int s){
    for(int i=0;i<18;i++){cout<<get(s,i);}
}
//en-code: 2-force, 1-force, [dual]
int encode(int n1,int n0,int p){
    int ans=0;
    ans=ans*3+n1;
    ans=ans*3+n0;
    ans=ans*2+p;
    return ans;
}
void decode(int s,int &n1,int &n0,int &p){
    p=s%2;s/=2;
    n0=s%3;s/=3;
    n1=s%3;s/=3;
}
int trans(int n2,int n1,int n0,int jiang){
    if(jiang){
        if(n0<2) return -1;
        n0-=2;
    }
    if(n0<n1+n2) return -1;
    n0-=n1+n2;//交够国家的，留给集体的
    //剩下都是自己的
    if(n0>=3) n0-=3;
    return n0;
}
int state_goto(int s0,int n0,int jiang){
    int n2,n1,p;
    decode(s0,n2,n1,p);
    if(p&&jiang) return -1;
    int t0=trans(n2,n1,n0,jiang);
    if(t0==-1) return -1;
    return encode(n1,t0,p|jiang);
}
int VM_goto(int vm0,int n0){
    int vm1=0;
    for(int s0=0;s0<3*3*2;s0++){
        if(!get(vm0,s0)) continue;
        for(int p=0;p<=1;p++){
            int s1=state_goto(s0,n0,p);
            if(s1!=-1){
                vm1=change(vm1,s1,1);
            }
        }
    }
    return vm1;
}
map<int,int> Dict;
int cnt=0;
int table[SIZEN][SIZEN]={0};
bool success[SIZEN]={0};
queue<int> Q;
bool add_state(int vm){
    if(!Dict.count(vm)){
        Dict[vm]=cnt;
        Q.push(vm);
        if(get(vm,encode(0,0,1))) success[cnt]=true;
        cnt++;
        return true;
    }
    return false;
}
void BFS_states(void){
    int vm0=0;
    vm0=change(vm0,encode(0,0,0),1);
    add_state(vm0);
    while(!Q.empty()){
        vm0=Q.front();Q.pop();
        for(int i=0;i<=4;i++){
            int vm1=VM_goto(vm0,i);
            add_state(vm1);
            table[Dict[vm0]][i]=Dict[vm1];
        }
    }
}
int N,M;
int F[SIZEN][SIZEN][SIZEN];
void add(int &a,int b){
    a+=b;
    a%=MOD;
}
void work(void){
    static int kase=0;
    int vm0=0;
    vm0=change(vm0,encode(0,0,0),1);
    memset(F,0,sizeof(F));
    F[0][0][Dict[vm0]]=1;
    for(int i=1;i<=N+3;i++){
        int h=i>N?0:4;
        for(int j=0;j<=M;j++){
            for(int id=0;id<cnt;id++){
                if(!F[i-1][j][id]) continue;
                for(int n0=0;n0<=h&&j+n0<=M;n0++){
                    int id1=table[id][n0];
                    add(F[i][j+n0][id1],F[i-1][j][id]);
                }
            }
        }
    }
    int ans=0;
    for(int id=0;id<cnt;id++){
        if(!success[id]) continue;
        add(ans,F[N+3][M][id]);
    }
    printf("Case #%d: %d\n",++kase,ans);
}
int main(void){
    freopen("mahjong.in","r",stdin);
    freopen("mahjong.out","w",stdout);
    BFS_states();
    int T;scanf("%d",&T);
    while(T--){
        scanf("%d%d",&N,&M);
        work();
    }
    return 0;
}