結果

問題 No.741 AscNumber(Easy)
ユーザー sute akasute aka
提出日時 2021-10-08 16:59:31
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 290 ms / 2,000 ms
コード長 8,536 bytes
コンパイル時間 2,668 ms
コンパイル使用メモリ 206,032 KB
最終ジャッジ日時 2025-01-24 21:41:00
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 55
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#ifdef _MSC_VER
#include <ppl.h>
#else
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#endif
/* const */
constexpr double PI = 3.141592653589793238462643;
/* io */
#define endl '\n'
namespace aux {
template <typename T, unsigned N, unsigned L>
struct tp {
    static void print(std::ostream& os, const T& v) {
        os << std::get<N>(v) << ", ";
        tp<T, N + 1, L>::print(os, v);
    }
};
template <typename T, unsigned N>
struct tp<T, N, N> {
    static void print(std::ostream& os, const T& v) { os << std::get<N>(v); }
};
}  // namespace aux
template <typename... Ts>
std::ostream& operator<<(std::ostream& os, const std::tuple<Ts...>& t) {
    os << '[';
    aux::tp<std::tuple<Ts...>, 0, sizeof...(Ts) - 1>::print(os, t);
    os << ']';
    return os;
}
template <class T, class = typename T::iterator, std::enable_if_t<!std::is_same<T, std::string>::value, int> = 0>
std::ostream& operator<<(std::ostream& os, T const& a);
template <class T, class S>
std::ostream& operator<<(std::ostream& os, std::pair<T, S> const& p) { return os << '[' << p.first << ", " << p.second << ']'; }
template <class T, class S>
std::istream& operator>>(std::istream& is, std::pair<T, S>& p) { return is >> p.first >> p.second; }
template <class T, class, std::enable_if_t<!std::is_same<T, std::string>::value, int>>
std::ostream& operator<<(std::ostream& os, T const& a) {
    bool f = true;
    os << '[';
    for (auto const& x : a) {
        os << (f ? "" : ", ") << x;
        f = false;
    }
    os << ']';
    return os;
}
template <class T, size_t N, std::enable_if_t<!std::is_same<T, char>::value, int> = 0>
std::ostream& operator<<(std::ostream& os, const T (&a)[N]) {
    bool f = true;
    os << '[';
    for (auto const& x : a) {
        os << (f ? "" : ", ") << x;
        f = false;
    }
    os << ']';
    return os;
}
template <class T, class = decltype(std::begin(std::declval<T&>())), class = typename std::enable_if<!std::is_same<T, std::string>::value>::type>
std::istream& operator>>(std::istream& is, T& a) {
    for (auto& x : a) is >> x;
    return is;
}
struct IOSetup {
    IOSetup(bool f) {
        if (f) {
            std::cin.tie(nullptr);
            std::ios::sync_with_stdio(false);
        }
        std::cout << std::fixed << std::setprecision(15);
    }
} iosetup(true);
/* format */
template <typename... Ts>
std::string format(const std::string& f, Ts... t) {
    size_t l = std::snprintf(nullptr, 0, f.c_str(), t...);
    std::vector<char> b(l + 1);
    std::snprintf(&b[0], l + 1, f.c_str(), t...);
    return std::string(&b[0], &b[0] + l);
}
/* dump */
#define ENABLE_DUMP
#ifdef ENABLE_DUMP
#define DUMPOUT std::cerr
std::ostringstream DUMPBUF;
#define dump(...)                                                                                  \
    do {                                                                                           \
        DUMPBUF << "  ";                                                                           \
        DUMPBUF << #__VA_ARGS__ << " :[DUMP - " << __LINE__ << ":" << __FUNCTION__ << "]" << endl; \
        DUMPBUF << "    ";                                                                         \
        dump_func(__VA_ARGS__);                                                                    \
        DUMPOUT << DUMPBUF.str();                                                                  \
        DUMPBUF.str("");                                                                           \
        DUMPBUF.clear();                                                                           \
    } while (0);
void dump_func() { DUMPBUF << endl; }
template <class Head, class... Tail>
void dump_func(Head&& head, Tail&&... tail) {
    DUMPBUF << head;
    if (sizeof...(Tail) == 0) {
        DUMPBUF << " ";
    } else {
        DUMPBUF << ", ";
    }
    dump_func(std::move(tail)...);
}
#else
#define dump(...) void(0);
#endif
/* misc */
struct Xorshift {
    uint64_t x = 88172645463325252LL;
    void set_seed(unsigned seed, int rep = 100) {
        x = (seed + 1) * 10007;
        for (int i = 0; i < rep; i++) next_int();
    }
    unsigned next_int() {
        x = x ^ (x << 7);
        return x = x ^ (x >> 9);
    }
    unsigned next_int(unsigned mod) {
        x = x ^ (x << 7);
        x = x ^ (x >> 9);
        return x % mod;
    }
    unsigned next_int(unsigned l, unsigned r) {
        x = x ^ (x << 7);
        x = x ^ (x >> 9);
        return x % (r - l + 1) + l;
    }
    double next_double() { return double(next_int()) / UINT_MAX; }
} rnd;
template <typename T>
void shuffle_vector(std::vector<T>& v, Xorshift& rnd) {
    int n = v.size();
    for (int i = n - 1; i >= 1; i--) {
        int r = rnd.next_int(i);
        std::swap(v[i], v[r]);
    }
}
std::vector<std::string> split(std::string str, const std::string& delim) {
    for (char& c : str)
        if (delim.find(c) != std::string::npos) c = ' ';
    std::istringstream iss(str);
    std::vector<std::string> parsed;
    std::string buf;
    while (iss >> buf) parsed.push_back(buf);
    return parsed;
}

#define rep(i, m, n) for (int i = (int)(m); i < (int)(n); i++)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)

template <class T>
bool chmax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T& a, const T& b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
template <typename T, typename... Args>
auto make_vector(T x, int arg, Args... args) {
    if constexpr (sizeof...(args) == 0)
        return std::vector<T>(arg, x);
    else
        return std::vector(arg, make_vector<T>(x, args...));
}
template <typename T = int>
T modpow(T n, T e, T m) {
    T result = 1;
    while (e > 0) {
        if (e & 1) result = (result * n) % m;
        e >>= 1;
        n = (n * n) % m;
    }
    return result;
}

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using pdd = pair<double, double>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
#define fore(i, a) for (auto& i : a)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define pb push_back
#define append emplace_back

constexpr ll INFLL = INT64_MAX;
constexpr int INF = INT_MAX;
constexpr ll MOD = 1000000007;
constexpr ll mod = 998244353;
template <typename T>
using pq = priority_queue<T, vector<T>, greater<T>>;

template <uint64_t MOD>
class modint {
    using u64 = uint64_t;

   public:
    u64 x;
    constexpr modint(const u64 x = 0) noexcept : x(x % MOD) {}
    constexpr u64& value() noexcept { return x; }
    constexpr const u64& value() const noexcept { return x; }
    constexpr modint operator+(const modint r) const noexcept { return modint(*this) += r; }
    constexpr modint operator-(const modint r) const noexcept { return modint(*this) -= r; }
    constexpr modint operator*(const modint r) const noexcept { return modint(*this) *= r; }
    constexpr modint operator/(const modint r) const noexcept { return modint(*this) /= r; }
    constexpr modint& operator+=(const modint r) noexcept {
        x += r.x;
        if (x >= MOD) x -= MOD;
        return *this;
    }
    constexpr modint& operator-=(const modint r) noexcept {
        if (x < r.x) x += MOD;
        x -= r.x;
        return *this;
    }
    constexpr modint& operator*=(const modint r) noexcept {
        x = x * r.x % MOD;
        return *this;
    }
    constexpr modint& operator/=(modint r) noexcept {
        u64 exp = MOD - 2;
        while (exp) {
            if (exp % 2) *this *= r;
            r *= r;
            exp /= 2;
        }
        return *this;
    }
    friend istream& operator>>(istream& in, modint& m) {
        in >> m.x;
        return in;
    }
    friend ostream& operator<<(ostream& out, const modint& m) {
        out << m.x;
        return out;
    }
};
using mint = modint<MOD>;

int main() {
#if 1
    ios::sync_with_stdio(false);
    cin.tie(0);
#endif
    int N;
    cin >> N;

    auto dp = make_vector<mint>(0, N + 1, 10);
    dp[0][0] = 1;
    rep(i, 0, N) {
        rep(j, 0, 10) {
            rep(x, j, 10) {
                dp[i + 1][max(j, x)] += dp[i][j];
            }
        }
    }
    mint res = 0;
    rep(i, 0, 10) res += dp[N][i];
    cout << res << endl;
}
0