結果
問題 | No.741 AscNumber(Easy) |
ユーザー |
|
提出日時 | 2024-07-31 23:29:35 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 594 ms / 2,000 ms |
コード長 | 2,081 bytes |
コンパイル時間 | 5,314 ms |
コンパイル使用メモリ | 302,876 KB |
実行使用メモリ | 183,980 KB |
最終ジャッジ日時 | 2024-07-31 23:29:50 |
合計ジャッジ時間 | 14,576 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 55 |
ソースコード
// #undef _GLIBCXX_DEBUG// #undef LOCAL#pragma GCC optimize("Ofast")#pragma GCC optimize("unroll-loops")#include <bits/stdc++.h>using namespace std;#if __has_include(<atcoder/all>)#include <atcoder/all>using namespace atcoder;#endif#ifdef LOCAL#include "../algo/debug.hpp"#else#define debug(...) void(0)#endifconstexpr int inf = (1<<30) - 1;constexpr long long linf = (1LL<<60) - 1;using ll = long long;using ld = long double;#define len(x) int((x).size())#define all(x) begin(x), end(x)#define rall(x) rbegin(x), rend(x)#define LB(c, x) distance(begin(c), lower_bound(all(c), x))#define UB(c, x) distance(begin(c), upper_bound(all(c), x))template <typename T, typename S> inline auto min(const T& a, const S& b) { return(a < b ? a : b); }template <typename T, typename S> inline auto max(const T& a, const S& b) { return(a > b ? a : b); }template <typename T, typename S> inline bool chmax(T& a, const S& b) { return(a < b ? a = b, 1 : 0); }template <typename T, typename S> inline bool chmin(T& a, const S& b) { return(a > b ? a = b, 1 : 0); }// ------------------------------------------------------------------void solve() {int N; cin >> N;string S = "";while(N--) S += '9';int n = len(S);using mint = modint1000000007;vector dp(n + 1, vector<vector<mint>>(2, vector<mint>(10, 0)));dp[0][0][0] = 1;for(int i = 0; i < n; i++) {for(int j = 0; j < 2; j++) {for(int k = 0; k < 10; k++) {int lim = j ? 9 : S[i] - '0';for(int d = 0; d <= lim; d++) {if(k > d) continue;dp[i + 1][j || d < lim][d] += dp[i][j][k];}}}}mint ans = 0;for(int i = 0; i < 2; i++) {for(int j = 0; j < 10; j++) {ans += dp[n][i][j];}}cout << ans.val() << endl;}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);// fixed(cout).precision(12);int T = 1;// cin >> T;while(T--) {solve();}}