被3整除的子序列DP

我不是女神ヾ 2021-11-16 23:28 277阅读 0赞

链接：[https://ac.nowcoder.com/acm/problem/21302][https_ac.nowcoder.com_acm_problem_21302]  
来源：牛客网

给你一个长度为50的数字串,问你有多少个子序列构成的数字可以被3整除  
答案对1e9+7取模

## 输入描述: ##

输入一个字符串，由数字构成，长度小于等于50

## 输出描述: ##

输出一个整数

思路：这道题的转移很有意思，设dp\[i\]\[k\] 表示长度为 i 的数字串中模 3 等于 k 的子序列个数，其中（0<=k<=2）。

通过分析可以发现：

当第 i 个数模3等于0时：dp\[i\]\[0\] = 2\*dp\[i-1\]\[0\]+1; dp\[i\]\[1\] = 2\*dp\[i-1\]\[1\]; dp\[i\]\[2\] = 2\*dp\[i-1\]\[2\];

当第 i 个数模3等于1时：dp\[i\]\[0\] = dp\[i-1\]\[0\]+dp\[i-1\]\[2\]; dp\[i-1\]\[1\] = dp\[i-1\]\[1\]+dp\[i-1\]\[0\]+1; dp\[i\]\[2\] = dp\[i-1\]\[2\]+dp\[i-1\]\[1\];

当第 i 个数模3等于2时：dp\[i\]\[0\] = dp\[i-1\]\[0\]+dp\[i-1\]\[1\]; dp\[i-1\]\[1\] = dp\[i-1\]\[1\]+dp\[i-1\]\[2\]; dp\[i\]\[2\] = dp\[i-1\]\[2\]+dp\[i-1\]\[0\]+1;

#include<bits/stdc++.h>
    using namespace std;
    const int maxn = 3e6+10;
    const int modd = 1e9+7;
    typedef long long ll;
    const int inf = 0x3f3f3f3f;
    
    string s;
    int dp[100][5];
    int a[100];
    int main()
    {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cin>>s;
        int len = s.length();
        for(int i = 1;i <= len;i++){
            a[i] = s[i-1]-'0';
            if(a[i]%3 == 0){
                dp[i][0] = (2*dp[i-1][0]+1)%modd;
                dp[i][1] = (2*dp[i-1][1])%modd;
                dp[i][2] = (2*dp[i-1][2])%modd;
            }
            else if(a[i]%3 == 1){
                dp[i][0] = (dp[i-1][0]+dp[i-1][2])%modd;
                dp[i][1] = (dp[i-1][1]+dp[i-1][0]+1)%modd;
                dp[i][2] = (dp[i-1][2]+dp[i-1][1])%modd;
            }
            else if(a[i]%3 == 2){
                dp[i][0] = (dp[i-1][0]+dp[i-1][1])%modd;
                dp[i][1] = (dp[i-1][1]+dp[i-1][2])%modd;
                dp[i][2] = (dp[i-1][2]+dp[i-1][0]+1)%modd;
            }
        }
        cout<<dp[len][0]<<endl;
        return 0;
    }

[https_ac.nowcoder.com_acm_problem_21302]: https://ac.nowcoder.com/acm/problem/21302