牛客21302
作者:
RisingMoon
,
2023-03-22 21:42:02
,
所有人可见
,
阅读 158
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9+7;
const int N = 200005;
#define up(name,start,end,step) for(int name=start; name <= end; name += step)
#define down(name,start,end,step) for(int name=start; name >= end; name -= step)
long long f[55][4];
/*
f[i][j] 表示前i个字符组成的所有子串中,和的余数分别为0,1,2的数量
对于新加入的字符,如果之前共有n个子串,那么会新增n+1个子串
简单粗暴*
*/
void solve(){
string s;
cin >> s;
int n = s.length();
s = ' ' + s;
for(int i = 1; i <= n; ++ i){
s[i] = s[i]-'0';
}
for(int i = 1; i <= n; ++ i){
int last = s[i] % 3;
if(last == 0){
f[i][0] = (f[i-1][0]*2+1)%mod;
f[i][1] = (2*f[i-1][1])%mod;
f[i][2] = (2*f[i-1][2])%mod;
}
else if(last == 1){
f[i][0] = (f[i-1][2]+f[i-1][0])%mod;
f[i][1] = (f[i-1][0]+f[i-1][1]+1)%mod;
f[i][2] = (f[i-1][1]+f[i-1][2])%mod;
}
else if(last == 2){
f[i][0] = (f[i-1][1]+f[i-1][0])%mod;
f[i][1] = (f[i-1][1]+f[i-1][2])%mod;
f[i][2] = (f[i-1][2]+f[i-1][0]+1)%mod;
}
// printf("%d %lld %lld %lld\n",last,f[i][0],f[i][1],f[i][2]);
}
printf("%lld\n", f[n][0]);
return;
}
signed main(){
int t;
t=1;
while(t--)
solve();
return 0;
}