結果
問題 | No.741 AscNumber(Easy) |
ユーザー |
![]() |
提出日時 | 2019-08-20 00:01:16 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 530 ms / 2,000 ms |
コード長 | 2,552 bytes |
コンパイル時間 | 959 ms |
コンパイル使用メモリ | 114,244 KB |
実行使用メモリ | 81,536 KB |
最終ジャッジ日時 | 2024-10-05 11:59:50 |
合計ジャッジ時間 | 9,410 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 55 |
ソースコード
#include <algorithm>#include <bitset>#include <complex>#include <deque>#include <iostream>#include <istream>#include <iterator>#include <limits>#include <list>#include <map>#include <memory>#include <queue>#include <set>#include <stack>#include <string>#include <vector>#include <random>#include <tuple>#include <iomanip>#include <cstring>using namespace std;typedef long long ll;//typedef pair<int,int> Pint;//typedef pair<ll, ll> P;//typedef pair<ll, pair<ll, ll>> P;//typedef tuple<int,int,int> T;typedef vector<ll> vec;typedef vector<vec> mat;#define rep(i, n) for(ll i = 0; i < (n); i++)#define revrep(i, n) for(ll i = (n-1); i >= 0; i--)#define pb push_back#define f first#define s second//const ll INFL = 1LL << 60;//10^18 = 2^60const ll INFL = 1LL << 60;const int INF = 1 << 30;//10^9ll MOD = 1e9 + 7;//ll MOD = 998244353;vector<ll> dy = {0, 0, 1, -1, 1, 1, -1, -1, 0};vector<ll> dx = {1, -1, 0, 0, 1, -1, 1, -1, 0};ll max(ll a, ll b){return (a > b) ? a : b;}ll min(ll a, ll b){return (a < b) ? a : b;}ll pow_long(ll x, ll k){ll res = 1;while(k > 0){if(k % 2) res *= x;x *= x;k /= 2;}return res;}ll pow_mod(ll x, ll k){x %= MOD; x += MOD; x %= MOD;ll res = 1;while(k > 0){if(k % 2){res *= x; res %= MOD;}x *= x; x %= MOD;k /= 2;}return res;}ll inverse(ll x){return pow_mod(x, MOD - 2);};//最大公約数ll gcd(ll a, ll b){if(b == 0) return a;return gcd(b, a % b);}//最小公倍数ll lcm(ll x, ll y){return x / gcd(x, y) * y;};ll kai_mod(ll x){if(x == 0) return 1;return x * kai_mod(x-1) % MOD;}//コンビネーションconst int MAXcomb = 200010;ll fac[MAXcomb], finv[MAXcomb], inv[MAXcomb];//facはn!,finvは1/n!//invは逆元void COMinit(){fac[0] = fac[1] = 1;finv[0] = finv[1] = 1;inv[1] = 1;for(int i = 2; i < MAXcomb; i++){fac[i] = fac[i-1] * i % MOD;inv[i] = MOD - inv[MOD%i] * (MOD/i) % MOD;finv[i] = finv[i-1] * inv[i] % MOD;}}ll comb(int n, int k){if(n < k) return 0;if(n < 0 || k < 0) return 0;return fac[n] * finv[k] % MOD * finv[n-k] % MOD;}void solve(ll N){ll dp[N+1][10];rep(i, N+1)rep(j, 10) dp[i][j] = 0;dp[0][0] = 1;rep(i, N){rep(j, 10){for(ll k = j; k < 10; k++){dp[i+1][k] += dp[i][j];dp[i+1][k] %= MOD;}}}ll ans = 0;rep(i, 10) ans += dp[N][i];ans %= MOD;cout << ans << endl;}int main(void){ll N;cin >> N;solve(N);}