結果
問題 | No.741 AscNumber(Easy) |
ユーザー |
|
提出日時 | 2018-10-06 11:45:09 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 685 ms / 2,000 ms |
コード長 | 1,477 bytes |
コンパイル時間 | 980 ms |
コンパイル使用メモリ | 90,856 KB |
実行使用メモリ | 5,428 KB |
最終ジャッジ日時 | 2024-10-12 13:44:34 |
合計ジャッジ時間 | 10,907 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 55 |
ソースコード
#include <cmath>#include <iostream>#include <vector>using namespace std;using i64 = int64_t;constexpr int mod = static_cast<int>(powl(10, 9)) + 7;i64 f(string s) {int n = static_cast<int>(s.size());// dp[未満フラグ][先行ゼロでないか][前の数字] := パターン数vector<vector<vector<i64>>> dp(2, vector<vector<i64>>(2, vector<i64>(10, 0)));dp[0][0][0] = 1;for(int i=0; i<n; ++i) {vector<vector<vector<i64>>> ndp(2, vector<vector<i64>>(2, vector<i64>(10, 0)));for(int less=0; less<2; ++less) {for(int nuke0=0; nuke0<2; ++nuke0) {for(int before=0; before<10; ++before) {if(!dp[less][nuke0][before]) { continue; }int start = nuke0 ? before : 0;for(int d=start; d<=(less ? 9 : s[i]-'0'); ++d) {int nless = less || d < s[i] - '0',n_nuke0 = nuke0 || d > 0,nbefore = d;ndp[nless][n_nuke0][nbefore] += dp[less][nuke0][before];ndp[nless][n_nuke0][nbefore] %= mod;}}}}dp = ndp;}i64 res = 0;for(int less=0; less<2; ++less) {for(int nuke0=0; nuke0<2; ++nuke0) {for(int before=0; before<10; ++before) {res += dp[less][nuke0][before];res %= mod;}}}return res;}int main(void) {int n; scanf("%d", &n);string s = "";for(int i=0; i<n; ++i) {s += '9';}i64 res = f(s);printf("%ld\n", res);return 0;}