結果

問題 No.314 ケンケンパ
ユーザー LeonardoneLeonardone
提出日時 2015-12-07 06:16:03
言語 C++11
(gcc 11.4.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
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 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

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