数字串个数 参考代码

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int maxn = 10000 + 100;
const LL MOD = 1000000007;
LL dp[maxn][4];

LL fastPow(LL res, LL n) {
    LL ans;
    for (ans = 1; n != 0; n >>= 1) {
        if ((n & 1) == 1) {
            ans = ans * res % MOD;
        }
        res = res * res % MOD;
    }
    return ans;
}

int main() {
#ifdef ExRoc
    freopen("test.txt", "r", stdin);
#endif // ExRoc
    ios::sync_with_stdio(false);

    dp[0][0] = 1;
    for (int i = 1; i <= 10000; ++i) {
        dp[i][0] = dp[i - 1][0] * 7 % MOD;
        dp[i][1] = (dp[i - 1][0] * 1 + dp[i - 1][1] * 8 % MOD) % MOD;
        dp[i][2] = (dp[i - 1][0] + dp[i - 1][2] * 8 % MOD) % MOD;
        dp[i][3] = (dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][3] * 9) % MOD;
    }
    cout << dp[10000][3] << endl;

    cout << ((fastPow(9, 10000) - 2 * fastPow(8, 10000) + fastPow(7, 10000)) % MOD + MOD) % MOD << endl;

    return 0;
}