D 游游的9的倍数

题目描述

游游拿到了一个数字串，她想取一个该数字串的子序列（子序列在原串中可以不连续），使得该子序列是9的倍数。子序列可以包含前导零。
游游想知道，一共能取多少个合法的子序列？答案请对 \(10^9+7\) 取模。
我们定义，若两个子序列在原串中的位置不同，则认为它们不同。

输入描述

一个长度不超过200000的，仅由'0'~'9' 十种字符组成的字符串。

输出描述

子序列是9的倍数的数量。答案请对 \(10^9+7\) 取模。

解题思路

代码实现

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+100;
const int MOD=1e9+7;
int dp[N][10];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    string s;
    cin>>s;
    int n=s.size();
    dp[0][0]=1;
    for(int i=0;i<n;i++){
        //不选这个数字
        for(int j=0;j<9;j++){
            dp[i+1][j]=dp[i][j];
        }
        //选这个数字
        for(int j=0;j<9;j++){
            int l=(j+s[i]-'0')%9;
            dp[i+1][l]+=dp[i][j]; 
            dp[i+1][l]%=MOD;
        }
    }
    cout<<dp[n][0]-1<<"\n";
}