Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của ladpro98

#include <iostream>
#include <cstdio>
#include <algorithm>
const int MOD = 1000000007;
const int N = 100006;
using namespace std;
long long F[N], S[N];
int n, k;

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n >> k;
    if (n == 1) {if (k == 1) cout << 1; else cout << 0; return 0;}
    F[1] = 9; S[1] = 9;
    if (k == 1) F[1]--, S[1]--;
    for(int i = 2; i < k; i++) {
        F[i] = F[i - 1] * 10  % MOD;
        S[i] = (S[i - 1] + F[i]) % MOD;
    }
    if (k > 1) {
        F[k] = 10 * F[k - 1] - 1; S[k] = S[k - 1] + F[k];
    }
    for(int i = k + 1; i <= n; i++) {
        F[i] = (S[i - 1] - S[i - k - 1] + MOD) * 9 % MOD;
        S[i] = (S[i - 1] + F[i]) % MOD;
    }
    long long P = 1;
    for(int i = 1; i < n; i++)
        P = P * 10 % MOD;
    cout << (P * 10 - P - F[n] + MOD) % MOD;
    return 0;
}

Code mẫu của skyvn97

#include<cstdio>
#include<vector>
#define MAX   100100
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
using namespace std;
const int mod=(int)1e9+7;
int f[MAX][10][2],s[MAX][10][2];
int n,k;
inline void add(int &x,const int &y) {
    x+=y;
    if (x>=mod) x-=mod;
}
inline void sub(int &x,const int &y) {
    x-=y;
    if (x<0) x+=mod;
}
void process(void) {
    scanf("%d%d",&n,&k);
    FOR(i,1,9) {
        add(f[1][i][i==6 && k==1],1);
        add(s[1][i][i==6 && k==1],1);
    }
    FOR(i,2,n) REP(dig,10) REP(ok,2) {
        if (dig!=6) {
            if (!ok && dig>0) add(f[i][dig][ok],1);
            REP(pre,10) if (pre!=dig) add(f[i][dig][ok],s[i-1][pre][ok]);
        } else {
            if (!ok) {
                if (i<k) add(f[i][dig][ok],1);
                REP(pre,10) if (pre!=dig) {
                    add(f[i][dig][ok],s[i-1][pre][ok]);
                    if (i>k) sub(f[i][dig][ok],s[i-k][pre][ok]);
                }
            } else {
                if (i>=k) add(f[i][dig][ok],1);
                REP(pre,10) if (pre!=dig) {
                    add(f[i][dig][ok],s[i-1][pre][true]);
                    if (i>k) add(f[i][dig][ok],s[i-k][pre][false]);
                }
            }
        }
        s[i][dig][ok]=s[i-1][dig][ok];
        add(s[i][dig][ok],f[i][dig][ok]);
    }
    int res=0;
    REP(i,10) add(res,f[n][i][true]);
    printf("%d",res);
}
int main(void) {    
    process();
    return 0;
}