結果
問題 | No.314 ケンケンパ |
ユーザー |
|
提出日時 | 2015-12-07 06:06:09 |
言語 | C++11 (gcc 13.3.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,102 bytes |
コンパイル時間 | 1,024 ms |
コンパイル使用メモリ | 73,096 KB |
実行使用メモリ | 15,744 KB |
最終ジャッジ日時 | 2024-09-14 18:05:04 |
合計ジャッジ時間 | 5,306 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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) {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;c = min(c, n - c);for (ull i = 1ULL; i <= c; i++) {r *= n--;r /= i;}r %= UMD;mp[n][c] = 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)) % UMD;i += 2ULL;d -= 3LL;}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; }