被3整除的子序列 题解
被3整除的子序列
https://ac.nowcoder.com/acm/problem/21302
被3整除的子序列
第一次推转移方程
设该数字一共有n位，由1~n遍历，前i位能被3整除的个数分为两部分：一是第i-1位能被3整除的个数，二是第i位对3取模的余数与第i-1位的余数相加结果等于3的个数
我用第一个样例为例子：132
用第一层控制第i位数
i=1 1
i=2 13
i=3 132
| 0 | 1 | 0 |
| 1 | 2 | 0 |
| 3 | 2 | 2 |
当i=1时，之前没有能被3整除的数；
当i=2时，之前没有能被3整除的数，但是自身能被3整除，且正好是(0+0)%3=0，所以也为0。其它的位置也要进行更新。
当i=3时，之前有1个被3整除的数，且当前余数为2，与i-1中余数为1的数加起来正好能被3整除 (2+1)%3=0。
总个数为i=3（132）时，余数为0的位置的结果。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
ll dp[55][4];
int main(){
string s;
cin>>s;
int len=s.size();
for(int i=1;i<=len;i++){
int m=(s[i-1]-'0')%3;
dp[i][m]+=1;
for(int j=0;j<3;j++){
dp[i][j]+=(dp[i-1][j]+dp[i-1][(j+3-m)%3])%mod;
}
}
cout<<dp[len][0];
return 0;
} 
查看8道真题和解析