結果
問題 | No.741 AscNumber(Easy) |
ユーザー |
|
提出日時 | 2023-02-20 23:41:56 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 462 ms / 2,000 ms |
コード長 | 4,163 bytes |
コンパイル時間 | 1,887 ms |
コンパイル使用メモリ | 176,060 KB |
実行使用メモリ | 276,668 KB |
最終ジャッジ日時 | 2024-07-21 13:29:52 |
合計ジャッジ時間 | 9,587 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 55 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;using vi = vector<int>;using vll = vector<ll>;using vvi = vector<vi>;using vvll = vector<vll>;using vvvll = vector<vvll>;using vs = vector<string>;const int IntINF = 1 << 30;const ll LLINF = 1LL << 60;#define REP(i, a, n) for (ll i = (a); i < (ll)(n); ++i)#define rep(i, n) REP(i, 0, n)#define what_is(x) cerr << #x << " is " << x << endl;template <typename T1, typename T2>ostream &operator<<(ostream &os, const pair<T1, T2> &p) {os << p.first << " " << p.second;return os;}template <typename T> ostream &operator<<(ostream &os, const vector<T> &v) {rep(i, v.size()) { os << v[i] << (i < (ll)v.size() - 1 ? " " : ""); }return os;}template <typename T>ostream &operator<<(ostream &os, const vector<vector<T>> &v) {rep(i, v.size()) {rep(j, v[i].size()) {os << v[i][j] << (j < (ll)v[i].size() - 1 ? " " : "");}os << endl;}return os;}template <typename T, typename U>ostream &operator<<(ostream &os, const map<T, U> &v) {for (const auto &p : v) {os << p.first << ": " << p.second << endl;}return os;}inline void io_setup(int precision = 15) {cin.tie(nullptr);ios::sync_with_stdio(false);cout << fixed << setprecision(precision);cerr << fixed << setprecision(precision);}constexpr int MOD1 = 1000000007;constexpr int MOD2 = 998244353;constexpr int MOD3 = 1000000009;template <int MOD> struct Mint {long long val;constexpr Mint(long long v = 0) noexcept : val(v % MOD) {if (val < 0)v += MOD;}constexpr int get_mod() { return MOD; }constexpr Mint operator-() const noexcept { return val ? MOD - val : 0; }constexpr Mint operator+(const Mint &r) const noexcept {return Mint(*this) += r;}constexpr Mint operator-(const Mint &r) const noexcept {return Mint(*this) -= r;}constexpr Mint operator*(const Mint &r) const noexcept {return Mint(*this) *= r;}constexpr Mint &operator+=(const Mint &r) noexcept {val += r.val;if (val >= MOD)val -= MOD;return *this;}constexpr Mint &operator-=(const Mint &r) noexcept {val -= r.val;if (val < 0)val += MOD;return *this;}constexpr Mint &operator*=(const Mint &r) noexcept {val = val * r.val % MOD;return *this;}constexpr bool operator==(const Mint &r) const noexcept {return this->val == r.val;}constexpr bool operator!=(const Mint &r) const noexcept {return this->val != r.val;}friend constexpr istream &operator>>(istream &is, Mint<MOD> &x) noexcept {is >> x.val;x.val %= MOD;if (x.val < 0)x.val += MOD;return is;}friend constexpr ostream &operator<<(ostream &os,const Mint<MOD> &x) noexcept {return os << x.val;}};template <typename T> struct ModBinomialCoefficient {private:vector<T> fact, inv, fact_inv;public:constexpr ModBinomialCoefficient(int n) noexcept: fact(n, 1), inv(n, 1), fact_inv(n, 1) {int MOD = fact[0].get_mod();for (int i = 2; i < n; ++i) {fact[i] = fact[i - 1] * i;inv[i] = -inv[MOD % i] * (MOD / i);fact_inv[i] = fact_inv[i - 1] * inv[i];}}constexpr T combination(int n, int k) const noexcept {if (n < k || n < 0 || k < 0)return 0;return fact[n] * fact_inv[k] * fact_inv[n - k];}};using Mint1 = Mint<MOD1>;using Mint2 = Mint<MOD2>;using Mint3 = Mint<MOD3>;using vMint1 = vector<Mint1>;using vvMint1 = vector<vMint1>;using vvvMint1 = vector<vvMint1>;int main() {io_setup();int N;cin >> N;vvvMint1 dp(N + 1, vvMint1(2, vMint1(10, 0)));dp[0][0][9] = 1;rep(i, N) {int D = 9;rep(smaller, 2) {rep(j, 10) {if (smaller == 0) {rep(d, min(D + 1, (int)j + 1)) {dp[i + 1][d == D ? 0 : 1][d] += dp[i][smaller][j];}} else {rep(d, j + 1) { dp[i + 1][smaller][d] += dp[i][smaller][j]; }}}}}Mint1 ans = 0;rep(i, 10) { ans += dp[N][0][i] + dp[N][1][i]; }cout << ans << endl;return 0;}