結果
問題 | No.314 ケンケンパ |
ユーザー |
|
提出日時 | 2015-12-07 06:16:03 |
言語 | C++11 (gcc 13.3.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,159 bytes |
コンパイル時間 | 645 ms |
コンパイル使用メモリ | 73,076 KB |
実行使用メモリ | 18,752 KB |
最終ジャッジ日時 | 2024-09-14 18:08:37 |
合計ジャッジ時間 | 5,057 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | -- * 3 |
other | TLE * 1 -- * 16 |
ソースコード
// 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;while (d >= 0LL) {c = (c + cmb(ull(d) + i, i));i += 2ULL;d -= 3LL;if ((d & 1023LL) == 512LL) continue;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; }