結果

問題 No.314 ケンケンパ
ユーザー Leonardone
提出日時 2015-12-07 06:13:24
言語 C++11
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 1,173 bytes
コンパイル時間 717 ms
コンパイル使用メモリ 73,204 KB
実行使用メモリ 15,744 KB
最終ジャッジ日時 2024-09-14 18:05:58
合計ジャッジ時間 5,122 ms
ジャッジサーバーID
(参考情報)
judge2 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample -- * 3
other TLE * 1 -- * 16
権限があれば一括ダウンロードができます

ソースコード

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;
int k = 10;
while (d >= 0LL) {
c = (c + cmb(ull(d) + i, i));
i += 2ULL;
d -= 3LL;
if (--k) continue;
k = 10;
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; }
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0