是的,我又去偷题面了
解析在代码里
#include <bits/stdc++.h>
#define int long long
using namespace std ;
const int maxn = 1e3+105 ;
const int ha = 1e9+7 ;
int f[maxn][12][12] , ans ;
// f[i][j][k] -> 第i位上的数字是j,i-1的数字是k的不是萌数的个数是多少
string l , r ;
int calc (string s) {
int n = s.size() , X = -1 , Y = -1 ;// X , Y 分别记录i位相邻俩个数位
int tot = 0 , ans = 0 , flag = 0 ;
for(int i = 0 ; i < n ; i ++) {//把字符串转成数字,(因为用到了补集的思想)
tot = (tot * 10 + s[i]-'0'+ha) % ha ;
}
for(int i = 1 ; i < n ; i ++) { // 处理len位之前的,保证都是合法的
for(int j = 1 ; j <= 9 ; j ++) {//枚举当前位置的数字
for(int k = 0 ; k <= 9 ; k ++) {//枚举下一位的数字
ans = (ans+f[i][j][k]) % ha ;
}
}
}
for(int i = n ; i > 1 ; i --) {//枚举位数
int v = s[n-i] - '0' ;//倒着来(从低位到高位);
for(int j = 0 ; j < v ; j ++) {//枚举当前位置上的每一个数字
if(i != n || j != 0) {//如果首位不是0(首位不能是0哎)
for(int k = 0 ; k <= 9 ; k ++) {//枚举i-1位
if(X != j && Y != j && j != k && k != X) {//如果不是萌数
ans = (ans+f[i][j][k]) % ha ;//就加到补集里
}
}
}
}
if(v == X || v == Y) {
flag = 1 ;
break ;
}Y = X ; X = v ;
}
if(n > 1) ans += 10 ;//加上个位数
if(!flag) {
for(int j = 0 ; j <= s[n-1] - '0' ; j ++) {
if(j != Y && j != X) {
ans = (ans+1)%ha ;
}
}
}
return (tot-ans+1+ha)%ha ;//求补集
}
signed main () {
cin >> l >> r ;
for(int i = 2 ; i <= 1000 ; i ++) { //枚举位数
for(int j = 0 ; j <= 9 ; j ++) {//枚举i位上的数字
for(int k = 0 ; k <= 9 ; k ++) {//枚举i+1位上的数字
if(j != k) //如果这两位上的数字不同
{
for(int o = 0 ; o <= 9 ; o ++) {//枚举第i-1位的数字
if(j!=o&&k!=o) {// 如果再不同的话,就不是萌数了
f[i][j][k] = (f[i][j][k]+f[i-1][k][o])%ha ;
}
}
if(i-1 == 1) f[i][j][k] = (f[i][j][k]+1)%ha ; //如果上一位是一位数,ans++(一位数也是非萌数)
}
}
}
}
// int m = s.size() ;
ans = (calc(r)-calc(l)+ha)%ha ;//[l,r] 可以差分成 [0,r] - [0,l-1] ;
for(int i = 1 ; i < l.size() ; i ++ ) {//但是由于l是个该死的字符串
if(l[i] == l[i-1] || (i > 1 && l[i] == l[i-2])) {//暴力判断第l个数是不是
ans = (ans+1) % ha ;
break ;
}
}
printf("%lld
",ans) ;
return 0 ;
}