hdu 4758 Walk Through Squares（自動機+DP）

Walk Through Squares

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65535/65535 K (Java/Others)

Total Submission(s): 788    Accepted Submission(s): 216

Problem Description

  On the beaming day of 60th anniversary of NJUST, as a military college which was Second Artillery Academy of Harbin Military Engineering Institute before, queue phalanx is a special landscape.

  Here is a M*N rectangle, and this one can be divided into M*N squares which are of the same size. As shown in the figure below:

  01--02--03--04

  || || || ||

  05--06--07--08

  || || || ||

  09--10--11--12

  Consequently, we have (M+1)*(N+1) nodes, which are all connected to their adjacent nodes. And actual queue phalanx will go along the edges.

  The ID of the first node,the one in top-left corner,is 1. And the ID increases line by line first ,and then by column in turn ,as shown in the figure above.

  For every node,there are two viable paths:

  (1)go downward, indicated by 'D';

  (2)go right, indicated by 'R';

  The current mission is that, each queue phalanx has to walk from the left-top node No.1 to the right-bottom node whose id is (M+1)*(N+1).

In order to make a more aesthetic marching, each queue phalanx has to conduct two necessary actions. Let's define the action:

  An action is started from a node to go for a specified travel mode.

  So, two actions must show up in the way from 1 to (M+1)*(N+1).

  For example, as to a 3*2 rectangle, figure below:

    01--02--03--04

    || || || ||

    05--06--07--08

    || || || ||

    09--10--11--12

  Assume that the two actions are (1)RRD (2)DDR

  As a result , there is only one way : RRDDR. Briefly, you can not find another sequence containing these two strings at the same time.

  If given the N, M and two actions, can you calculate the total ways of walking from node No.1 to the right-bottom node ?  

Input   The first line contains a number T,(T is about 100, including 90 small test cases and 10 large ones) denoting the number of the test cases.

  For each test cases,the first line contains two positive integers M and N(For large test cases,1<=M,N<=100, and for small ones 1<=M,N<=40). M denotes the row number and N denotes the column number.

  The next two lines each contains a string which contains only 'R' and 'D'. The length of string will not exceed 100. We ensure there are no empty strings and the two strings are different.

Output   For each test cases,print the answer MOD 1000000007 in one line.

Sample Input

2
3 2
RRD
DDR
3 2
R
D
        

Sample Output

1
10
        

Source 2013 ACM/ICPC Asia Regional Nanjing Online  

題意：有一個(M+1)*(N+1)的方陣，從左上角走到右下角，且隻能往右或者往下，R表示往右，D表示往下，這樣得出很多種隻包含R和D的序列，問同時包含子串1和2的序列有多少種

題解：将子串1和2構成包含失敗指針的trie樹，這樣就得到很多種不同的狀态，對于這些狀态作dp，dp【x】【y】【now】【4】代表這個狀态的序列數，x和y分别代表坐标，now代表trie樹的狀态，最後的4是指是否已經包含子串1或者子串2的狀态壓縮，二進制來說00代表什麼都不包含，01代表包含子串1，10代表包含子串2，11代表包含2個子串，轉移方程見代碼，最後dp[n][m][i][3]，周遊所有狀态i的和，就是答案了

#include<stdio.h>
#include<string.h>
#include<queue>
#define mod 1000000007
using namespace std;
struct tree{
    int fail,flag,next[2];
    void init()
    {
        fail=flag=0;
        next[0]=next[1]=-1;
    }
}tree[208];
char s[108];
int n,m,all;
int dp[103][103][203][4];
void myinsert(int x)
{
    int now=0,temp,i;

    for(i=0;s[i];i++)
    {
        temp=s[i]=='R'?0:1;
        if(tree[now].next[temp]==-1)
        {
            tree[now].next[temp]=++all;
            tree[all].init();
        }
        now=tree[now].next[temp];
    }
    tree[now].flag|=x;
}
void mybuildac()
{
    queue<int> q;
    int i,now=0;

    tree[now].fail=0;
    for(i=0;i<2;i++)
    {
        if(tree[now].next[i]==-1) tree[now].next[i]=0;
        else
        {
            tree[tree[now].next[i]].fail=0;
            q.push(tree[now].next[i]);
        }
    }
    while(!q.empty())
    {
        now=q.front();
        q.pop();
        tree[now].flag|=tree[tree[now].fail].flag;
        for(i=0;i<2;i++)
        {
            if(tree[now].next[i]==-1) tree[now].next[i]=tree[tree[now].fail].next[i];
            else
            {
                tree[tree[now].next[i]].fail=tree[tree[now].fail].next[i];
                q.push(tree[now].next[i]);
            }
        }
    }
}
int slove()
{
    int i,j,k,l,ans=0;

    memset(dp,0,sizeof(dp));
    dp[0][0][0][0]=1;
    for(i=0;i<=n;i++)
    {
        for(j=0;j<=m;j++)
        {
            for(k=0;k<=all;k++)
            {
                for(l=0;l<4;l++)
                {
                    if(j<m)
                    {
                        dp[i][j+1][tree[k].next[0]][l|tree[tree[k].next[0]].flag]+=dp[i][j][k][l];
                        if(dp[i][j+1][tree[k].next[0]][l|tree[tree[k].next[0]].flag]>=mod)
                            dp[i][j+1][tree[k].next[0]][l|tree[tree[k].next[0]].flag]%=mod;
                    }
                    if(i<n)
                    {
                        dp[i+1][j][tree[k].next[1]][l|tree[tree[k].next[1]].flag]+=dp[i][j][k][l];
                        if(dp[i+1][j][tree[k].next[1]][l|tree[tree[k].next[1]].flag]>=mod)
                            dp[i+1][j][tree[k].next[1]][l|tree[tree[k].next[1]].flag]%=mod;
                    }
                }
            }
        }
    }
    for(i=0;i<=all;i++) ans=(ans+dp[n][m][i][3])%mod;

    return ans;
}
int main()
{
    int i,t;

    //freopen("t.txt","r",stdin);
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&m,&n);
        tree[0].init();
        for(all=i=0;i<2;i++)
        {
            scanf("%s",s);
            myinsert(1<<i);
        }
        mybuildac();
        printf("%d\n",slove());
    }

    return 0;
}