https://yukicoder.me/problems/no/741
前提知識
解法
https://yukicoder.me/submissions/289853
この問題はN桁以下の数でAscNumberである数の個数を求めている。
桁DPをする。
DP[dgt][lst] := dgt桁まで確定していて最下位の桁の数がlstである組み合わせ
これは簡単な桁DPなので、実装する。
int N; mint dp[1010101][10]; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N; rep(i, 0, 10) dp[1][i] = 1; rep(i, 1, N) rep(lst, 0, 10) { rep(nxt, lst, 10) dp[i + 1][nxt] += dp[i][lst]; } mint ans = 0; rep(lst, 0, 10) ans += dp[N][lst]; cout << ans << endl; }