BZOJ 3934 CQOI 2015ロゴデザインプラグDP

問題:http://www.lydsy.com/JudgeOnline/problem.php?id=3934
プラグDPが思い浮かぶ.プラグの連通性を記録する必要はなく、プラグが存在するかどうかを記録するだけであることは明らかである.
1つのLを「下のプラグのみを含む格子--その下のいくつかの(ゼロにすることができる)上下のプラグを含む格子--1つの上のプラグ、1つの右のプラグを含む格子--その右のいくつかの(ゼロにすることができる)左右のプラグを含む格子--その右の1つの左のプラグを含む格子」の5つの部分から構成されていると見なす.
問題の意味によれば、各格子は2つのプラグを多く含み、2つのプラグを含む場合、3つだけが合法である.格ごとに押すときは、判断に注意してください.
現在の状態にいくつかの「L」の先頭が含まれていることを記録する必要があります.プラグのみを含む格子です.同時に、答えを統計するために、いくつかの「L」が終わったことを記録します.左のプラグしか入っていない格子をいくつか記入しました.この2つのものはそれぞれ2つのバイナリビットで記録することができます.
下のプラグのみを含む3つの格子、左のプラグのみを含む2つの格子を記入し、現在の決定格子が左のプラグのみを含む格子であってもよい場合、答えを更新する.
様々な状態の遷移は比較的簡単である.

#include
#include
#include
#define ll long long
#define MAXM 666666
#define Mod 23333
using namespace std;

int N,M,Map[35][35];
char s[35][35];
ll Ans;

int las[Mod],nex[MAXM],en[MAXM],tot;
void Add(int x,int y){
    en[++tot]=y;
    nex[tot]=las[x];
    las[x]=tot;
}

int cur,pre,total[2],En;
ll f[2][MAXM],state[2][MAXM];

void Ins(ll st,ll val){
    int p=st%Mod,i;
    for(i=las[p];i;i=nex[i])if(st==state[cur][en[i]]){
        f[cur][en[i]]+=val;
        return;
    }
    total[cur]++;
    state[cur][total[cur]]=st;
    f[cur][total[cur]]=val;
    Add(p,total[cur]);
}

ll Ec(ll st,int p,int q){
    return ((st<<4)|(p<<2)|q);
}

void PlugDP(){
    int i,j,k,d,r,p,q;
    ll st,tmp;

    cur=0;pre=1;    
    total[0]=1;state[0][1]=0;f[0][1]=1;
    En=(1<1)-1;

    for(i=1;i<=N;i++){
        for(j=1;j<=total[cur];j++)state[cur][j]=(state[cur][j]&15)|(state[cur][j]>>4<<5);
        for(j=1;j<=M;j++){
            cur^=1;pre^=1;
            total[cur]=0;
            memset(las,0,sizeof(las));tot=0;

            for(k=1;k<=total[pre];k++){
                st=state[pre][k]>>4;
                tmp=f[pre][k];
                r=st>>j-1&1;
                d=st>>j&1;
                q=state[pre][k]&3;
                p=(state[pre][k]&15)>>2;

                if(r&&d)continue;
                else if(!Map[i][j]){
                    if(!r&&!d)Ins(Ec(st,p,q),tmp);
                }
                else {
                    if(!r&&!d){
                        Ins(Ec(st,p,q),tmp);
                        if(p<3&&Map[i+1][j])Ins(Ec(st|(1<1),p+1,q),tmp);
                    }
                    else if(!r&&d){
                        if(Map[i][j+1])Ins(Ec(st,p,q),tmp);
                        if(Map[i+1][j])Ins(Ec(st^(1<1)^(1<q),tmp);
                    }
                    else {
                        if(Map[i][j+1])Ins(Ec(st^(1<1)^(1<q),tmp);
                        if(p==3&&q==2)Ans+=tmp;
                        else Ins(Ec(st^(1<1),p,q+1),tmp);
                    }
                }
            }

        }
    }
}

int main(){
    int i,j;
    scanf("%d%d",&N,&M);
    for(i=1;i<=N;i++)scanf("%s",&s[i][1]);
    for(i=1;i<=N;i++)
    for(j=1;j<=M;j++)if(s[i][j]=='.')Map[i][j]=1;
    PlugDP();
    printf("%lld
",Ans);
}