結果
問題 | No.314 ケンケンパ |
ユーザー | Leonardone |
提出日時 | 2015-12-07 06:14:26 |
言語 | C++11 (gcc 11.4.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,175 bytes |
コンパイル時間 | 707 ms |
コンパイル使用メモリ | 73,048 KB |
実行使用メモリ | 15,872 KB |
最終ジャッジ日時 | 2024-09-14 18:06:12 |
合計ジャッジ時間 | 5,136 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge6 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | TLE | - |
testcase_01 | -- | - |
testcase_02 | -- | - |
testcase_03 | -- | - |
testcase_04 | -- | - |
testcase_05 | -- | - |
testcase_06 | -- | - |
testcase_07 | -- | - |
testcase_08 | -- | - |
testcase_09 | -- | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
ソースコード
// yukicoder My Practice // author: Leonardone @ NEETSDKASU #include <iostream> #include <algorithm> #include <map> using namespace std; typedef long long ll; typedef unsigned long long ull; // const ll MD = 1000000007LL; const ull UMD = 1000000007ULL; map<ull,map<ull,ull> > mp; ull cmb(ull n, ull c) { c = min(c, n - c); auto x = mp.find(n); if (x != mp.end()) { auto y = x->second.find(c); if (y != x->second.end()) { return y->second; } } ull r = 1ULL; for (ull i = 1ULL; i <= c; i++) { r *= n--; r /= i; } r %= UMD; mp[c][n] = r; return r; } ull fnc(ll n) { ull c = 0ULL; ull i = 0ULL; if (n > 0LL && (n & 1LL)) { i = 1ULL; n -= 3LL; } ll d = n >> 1; int k = 100; while (d >= 0LL) { c = (c + cmb(ull(d) + i, i)); i += 2ULL; d -= 3LL; if (--k) continue; k = 100; c %= UMD; } return c; } void solve() { ll n; cin >> n; ull ans = (((fnc(n) + fnc(n - 1)) % UMD) + fnc(n - 2)) % UMD; cout << ans << endl; } int main() { solve(); return 0; }