結果
問題 | No.741 AscNumber(Easy) |
ユーザー |
|
提出日時 | 2023-04-05 17:29:44 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 510 ms / 2,000 ms |
コード長 | 2,461 bytes |
コンパイル時間 | 4,207 ms |
コンパイル使用メモリ | 250,752 KB |
最終ジャッジ日時 | 2025-02-11 23:04:17 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 55 |
ソースコード
#pragma region Macros#include <bits/stdc++.h>#if defined(LOCAL) || defined(ONLINE_JUDGE) || defined(_DEBUG)#include <atcoder/all>#endifusing namespace std;#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)#define REPR(i, n) for(int i=(n); i>=0; --i)#define FOR(i, n, m) for(int i=(m), i##_len=(n); i<i##_len; ++i)#define EACH(i, v) for(const auto& i : v)#define ALL(x) (x).begin(),(x).end()#define ALLR(x) (x).rbegin(),(x).rend()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<class T>using vec = vector<T>;template<class T, class U>using umap = unordered_map<T, U>;template<class T>using uset = unordered_set<T>;using ll = long long;using ld = long double;using P = pair<ll, ll>;//using T = tuple<ll, ll, ll>;using vl = vec<ll>;#define fi first#define se second#define el endlconstexpr ll INF = numeric_limits<ll>::max()/2-1;#pragma endregion#pragma region IOMacrostemplate<class T>istream &operator>>(istream &stream, vec<T>& o){REP(i, o.size())stream >> o[i];return stream;}template<class T>ostream &operator<<(ostream &stream, vec<T>& objs){REP(i, objs.size())stream << objs[i] << " ";stream << el;return stream;}#define I(T, ...) ;T __VA_ARGS__;__i(__VA_ARGS__);void __i() {}template<class T, class... Ts> void __i(T&& o, Ts&&... args){cin >> o;__i(forward<Ts>(args)...);}void O() {cerr << el;}template<class T, class... Ts> void O(T&& o, Ts&&... args){cerr << o << " ";O(forward<Ts>(args)...);}#pragma endregionvoid Main();int main(){std::cin.tie(nullptr);std::cout << std::fixed << std::setprecision(15);Main();return 0;}const ll mod = 1e9 + 7;ll dp[1000000+10][2][10];void init_dp(){memset(dp, -1ll, sizeof(dp));}ll KK;// sumの部分は、問題によってどうするか決めるll rec(int k = 0, bool tight = true, int mn = 0) {if (k == KK) {// sumがどうなっていたらOKなのか考えるreturn 1;}int x = 9;int e = (tight ? x : 9);auto &res = dp[k][tight][mn];if (~res) return res;res = 0;for (int i = mn; i <= e; ++i) {// sumの部分は問題によってどうするか決めるres += rec(k + 1, tight && i == e, max(mn, i));res %= mod;}return res;}void Main(){cin >> KK;init_dp();cout << rec() << el;}