是的,我又去偷题面了

解析在代码里

#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 ;
} 

溜了溜了!

01-11 00:50