1 条题解

  • 2
    @ 2021-05-27 23:09:31

    动态规划,设\(dp[i][j]\)是前\(i\)个字符中,末尾\(j\)个和"NJNU"的\(j\)个匹配,这样的字符串个数,则答案是\(3^n-dp[i][0..3]\)
    状态转移方程是:(注意取模)

    dp[i][0]=2*dp[i-1][0]+dp[i-1][1]+2*dp[i-1][2];
    dp[i][1]=dp[i-1][0]+dp[i-1][1]+dp[i-1][3];
    dp[i][2]=dp[i-1][1]+dp[i-1][3];
    dp[i][3]=dp[i-1][2];
    

    初始条件:

    dp[1][0]=2;dp[1][1]=1;
    

    即可。

    Code:

    #include<bits/stdc++.h>
    using namespace std;
    
    #define ll long long int
    const ll mod=1000000007;
    ll powmod(ll a,ll b){ll res=1;a%=mod; assert(b>=0);for(;b;b>>=1){if(b&1) res=res*a%mod;a=a*a%mod;}return res;}
    //Header
    
    const int maxn = 200005;
    ll dp[maxn][5];
    
    int main()
    {
        int n;cin>>n;
        dp[1][0]=2;dp[1][1]=1;
        for(int i=2;i<=n;i++)
        {
            dp[i][0]=2*dp[i-1][0]+dp[i-1][1]+2*dp[i-1][2];
            dp[i][1]=dp[i-1][0]+dp[i-1][1]+dp[i-1][3];
            dp[i][2]=dp[i-1][1]+dp[i-1][3];
            dp[i][3]=dp[i-1][2];
            for(int j=0;j<=3;j++) dp[i][j]%=mod;
        }
        cout<<(powmod(3,n)-(dp[n][0]+dp[n][1]+dp[n][2]+dp[n][3])+4*mod)%mod<<endl;
        return 0;
    }
    

    拓展
    滚动数组可以优化掉一维空间(虽然本题不需要)
    动态规划可以用矩阵快速幂优化,复杂度可以到达O(log n)

  • 1

信息

ID
1255
难度
7
分类
动态规划 点击显示
标签
递交数
164
已通过
17
通过率
10%
被复制
5
上传者