結果
問題 | No.741 AscNumber(Easy) |
ユーザー |
![]() |
提出日時 | 2018-10-05 21:38:40 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 18 ms / 2,000 ms |
コード長 | 1,183 bytes |
コンパイル時間 | 718 ms |
コンパイル使用メモリ | 77,960 KB |
実行使用メモリ | 11,056 KB |
最終ジャッジ日時 | 2024-10-12 12:56:51 |
合計ジャッジ時間 | 2,283 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 55 |
ソースコード
#include <iostream> #include <vector> #include <string> #include <algorithm> #include <cstdio> #include <cstring> #include <cmath> using namespace std; using ll = long long; constexpr int P = 1000000007; ll powmod(ll n, ll k) { ll r = 1, t = n % P; for (; k != 0; k /= 2) { if (k & 1) r = r * t % P; t = t * t % P; } return r; } ll inv(ll n) { return powmod(n, P - 2); } vector<int> f0, f1; void init(int n) { f0.resize(n + 1); f0[0] = 1; for (int i = 1; i <= n; i++) { f0[i] = (ll)f0[i - 1] * i % P; } f1.resize(n + 1); f1[n] = inv(f0[n]); for (int i = n; i > 0; i--) { f1[i - 1] = (ll)f1[i] * i % P; } } ll fact(int k) { return f0[k]; } ll comb(int n, int k) { if (n < k || k < 0) return 0; return (ll)f0[n] * f1[k] % P * f1[n - k] % P; } int inv(int n) { int m = P, y = 0, v = 1; while (1) { int q = m / n; int r = m % n; if (r == 0) return v < 0 ? v + P : v; y -= v * q; swap(y, v); m = n; n = r; } } int main() { int n; cin >> n; init(n + 9); cout << comb(9 + n, n) << endl; return 0; }