結果

問題 No.314 ケンケンパ
コンテスト
ユーザー Leonardone
提出日時 2015-12-07 06:07:25
言語 C++11（廃止可能性あり）
(gcc 13.3.0 + boost 1.89.0)
結果
TLE  
実行時間 -
コード長 1,102 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 760 ms
コンパイル使用メモリ 73,216 KB
実行使用メモリ 15,744 KB
最終ジャッジ日時 2024-09-14 18:05:12
合計ジャッジ時間 5,235 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other TLE * 1 -- * 16
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

// 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[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; }
0