牛客周赛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;
}
查看15道真题和解析