解析在代码里
#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\n",ans) ; return 0 ; }