携程4.14笔试第四题
给定一个长度为n的数字字符串s，包含字符0-9，求满足子序列是9的倍数的子序列个数，n <= 200000
示例：1188
输出：5
解释：4个’18‘，1个1188
思路：
观察可知：满足条件的子序列的按位和一定是9的倍数，例如 1 + 8 = 9， 1 + 1 + 8 + 8 = 18
设 f(i)(j) ：从 第 i 位到末位，按位和对9取余为 j 的子序列的个数
状态转移方程见代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int mod = 1e9 + 7;
const int N = 2e5 + 7;
int f[N][10];
int main() {
string s;
cin>>s;
int n = s.size();
int cnt[10];
memset(f, 0, sizeof f);
memset(cnt, 0, sizeof cnt);
int ans = 0;
for(int i = n - 1; i >= 0; i--) {
int key = (s[i] - '0') % 9;
for(int j = 0; j <= 8; j++) {
f[i][j] = f[i + 1][j];
}
f[i][key]++;
for(int j = 0; j <= 8; j++) {
int k = (j + key) % 9;
f[i][k] = (f[i][k] + f[i + 1][j])%mod;
}
}
cout<<f[0][0]<<"\n";
} 
投递CVTE等公司10个岗位 >
