牛客周赛ROUND1 D

游游的9的倍数

https://ac.nowcoder.com/acm/contest/60245/D

一般来说，要求符合条件的子序列的数量，而且子序列是不连续的（虽然子序***实都是不连续的）都可以考虑dp来做，一般的思路就是考虑从0~k号位置的子序列个数与0~k-1号位置的子序列个数之间的关系，找到状态转移方程

这题要找的是9倍，一般来说，如果0~k位子序列的和是9的倍数，第k位我们直接设为6，那么显然0~k-1位的余数为3的方案数就是0~k位选择了6的情况下和是9的倍数的方案数，这里就可以得到dp数组的第二个维度就是模9的余数

最后我们完善一下状态转移方程，上面是选了6，还可以不选6，0~k-1位余数为0的方案数直接加过来，还有一种情况，只选第k位的数，6的话就是加到dp[k][6]中

这样就能有一个完整的状态转移方程，从0遍历到len即可

#include<iostream>
#include<cstring>
const int M = 1000000007;
const int N = 200005;
using namespace std;
string s;
int ans;
long long a[N],dp[N][10];
int main()
{
    cin >> s;
    int len = s.length();
    for(int i = 0 ; i < len ; i++)
    {
        int k =  s[i] - '0';
        a[i+1] = k;
      dp[i+1][k%9] ++;//0和9属于同一种情况
       
    }
    int n =  len;
   // dp[0][0] =1;不需要这个，因为初始状态就是0没有方案
    for(int i = 1;  i <= n ; i++)
    {
      
        for(int j =  0; j <= 8 ; j++)
        {
            //cout<<dp[1][1]<<endl;
            dp[i][(j+a[i])%9] = (dp[i][(j+a[i])%9] + dp[i-1][j]+dp[i-1][(j+a[i])%9])%M;
          
           // cout<<i<<" "<<(j+a[i])%9<<" "<<dp[i][(j+a[i])%9]<<endl;
        }
    }
    cout << dp[n][0]%M << endl;
    return 0;
}