cf404d-白红宇

cf404d

阅读量：2506 次

发布时间：2019-05-11

本文共 2035 字，大约阅读时间需要 6 分钟。

d题一看就是一个dp的题目，因为常数很大为1000000，所以是一维的dp。

然后开始想发现要做一个有限自动机，有限自动机我就翻了一下编译原理那本绿书，很快就将自动机求了出来，然后把状态方程表示出来，就解决了。

有限自动机的图：

源代码：

#include 
   
    #include 
    
     #include 
     
      #define MOD 1000000007using namespace std;int dp[1111111][6];char s[1111111];int main(){//    freopen("data.in", "r", stdin);    scanf("%s", s);    int n = strlen(s);    if(s[0] == '?')    {        dp[0][1] = dp[0][2] = dp[0][3] = 1;        dp[0][4] = dp[0][5] = 0;    }else if(s[0] == '1')    {        dp[0][1] = dp[0][3] = dp[0][4] = dp[0][5] = 0;        dp[0][2] = 1;    }else if(s[0] == '2')    {        puts("0");        return 0;    }else if(s[0] == '*')    {        dp[0][1] = dp[0][2] = dp[0][4] = dp[0][5] = 0;        dp[0][3] = 1;    }else if(s[0] == '0')    {        dp[0][2] = dp[0][3] = dp[0][4] = dp[0][5] = 0;        dp[0][1] = 1;    }    for(int i = 1; i < n; i++)    {        if(s[i] == '?')        {            dp[i][1] = ((dp[i-1][1] + dp[i-1][3])%MOD + dp[i-1][4])%MOD;            dp[i][2] = (dp[i-1][1] + dp[i-1][3])%MOD;            dp[i][3] = ((dp[i-1][3] + dp[i-1][4])%MOD + dp[i-1][5])%MOD;            dp[i][4] = dp[i-1][2];            dp[i][5] = dp[i-1][4];        } else if(s[i] == '0')        {            dp[i][1] = dp[i-1][1];            dp[i][2] = 0;            dp[i][3] = 0;            dp[i][4] = 0;            dp[i][5] = 0;        } else if(s[i] == '1')        {            dp[i][1] = (dp[i-1][3] + dp[i-1][4])%MOD;            dp[i][2] = dp[i-1][1];            dp[i][3] = 0;            dp[i][4] = 0;            dp[i][5] = 0;        } else if(s[i] == '2')        {            dp[i][1] = 0;            dp[i][2] = dp[i-1][3];            dp[i][3] = 0;            dp[i][4] = 0;            dp[i][5] = dp[i-1][4];        } else if(s[i] == '*')        {            dp[i][1] = 0;            dp[i][2] = 0;            dp[i][3] = ((dp[i-1][3] + dp[i-1][4])%MOD + dp[i-1][5])%MOD;            dp[i][4] = dp[i-1][2];            dp[i][5] = 0;        }    }    printf("%d\n", ((dp[n-1][1] + dp[n-1][3])%MOD + dp[n-1][4])%MOD);    return 0;}