結果
問題 | No.741 AscNumber(Easy) |
ユーザー |
![]() |
提出日時 | 2020-12-09 21:35:37 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 614 ms / 2,000 ms |
コード長 | 2,657 bytes |
コンパイル時間 | 2,177 ms |
コンパイル使用メモリ | 191,292 KB |
最終ジャッジ日時 | 2025-01-16 20:58:54 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 55 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define rep(i, n) for (int i = 0; i < (int)(n); i++)#define ALL(v) (v).begin(), (v).end()using ll = long long;constexpr int INF = 1e9;constexpr long long LINF = 1e18;constexpr long long MOD = 1e9 + 7;/*実行時MODint :template <int& MOD = 1000000007>static int MOD;cin >> MOD;*/template <int MOD = 1000000007>struct Mint {int x;constexpr Mint() : x(0) {}constexpr Mint(long long t): x(t >= 0 ? (t % MOD) : (MOD - (-t) % MOD) % MOD) {}Mint pow(int n) {Mint res(1), t(x);while (n > 0) {if (n & 1) res *= t;t *= t;n >>= 1;}return res;}Mint inv() const {int a = x, b = MOD, u = 1, v = 0, t;while (b > 0) {t = a / b;a -= t * b;swap(a, b);u -= t * v;swap(u, v);}return Mint(u);}Mint &operator+=(Mint a) {x += a.x;if (x >= MOD) x -= MOD;return *this;}Mint &operator-=(Mint a) {x += MOD - a.x;if (x >= MOD) x -= MOD;return *this;}Mint &operator*=(Mint a) {x = int(1LL * x * a.x % MOD);return *this;}Mint &operator/=(Mint a) {return (*this) *= a.inv();}Mint operator+(Mint a) const {return Mint(x) += a;}Mint operator-(Mint a) const {return Mint(x) -= a;}Mint operator*(Mint a) const {return Mint(x) *= a;}Mint operator/(Mint a) const {return Mint(x) /= a;}Mint operator-() const {return Mint(-x);}bool operator==(const Mint a) {return x == a.x;}bool operator!=(const Mint a) {return x != a.x;}bool operator<(const Mint a) {return x < a.x;}friend ostream &operator<<(ostream &os, const Mint &a) {return os << a.x;}friend istream &operator>>(istream &is, Mint &a) {int t;is >> t;a = Mint<MOD>(t);return (is);}};int n;bool memo[1000001][2][10];Mint<> dp[1000001][2][10];Mint<> rec(int digit, bool tight, int last) {if (memo[digit][tight][last]) return dp[digit][tight][last];memo[digit][tight][last] = true;if (digit == n) return dp[digit][tight][last] = 1;Mint<> res = 0;for (int i = last; i <= 9; i++) {res += rec(digit + 1, tight && i == 9, i);}return dp[digit][tight][last] = res;}signed main() {cin >> n;cout << rec(0, true, 0) << endl;return 0;}