結果
問題 | No.93 ペガサス |
ユーザー |
![]() |
提出日時 | 2016-05-13 19:31:27 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 1,491 bytes |
コンパイル時間 | 508 ms |
コンパイル使用メモリ | 68,468 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-05 16:35:34 |
合計ジャッジ時間 | 1,250 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 16 |
ソースコード
#include <cstdio>#include <cassert>#include <cmath>#include <iostream>#include <vector>#define _fetch(_1, _2, _3, _4, name, ...) name#define rep2(i, n) rep3(i, 0, n)#define rep3(i, a, b) rep4(i, a, b, 1)#define rep4(i, a, b, c) for (int i = int(a); i < int(b); i += int(c))#define rep(...) _fetch(__VA_ARGS__, rep4, rep3, rep2, _)(__VA_ARGS__)using namespace std;using i64 = long long;using u32 = unsigned;using u64 = unsigned long long;void solve() {const u32 mod = 1e9 + 7;const u32 inv4 = (mod + 1) / 4;auto terms = vector<u32>({1, 1, 2, 2, 8, 28, 152, 952, 7208, 62296, 605864, 6522952, 76951496});int coefs[13][3] = {{22, 4, 0},{-38, -16, 0},{-3, -1, -2},{56, 79, 9},{-32, -74, -8},{28, -90, -14},{20, 116, 18},{-136, 64, 20},{8, -98, -22},{66, -6, -18},{39, 45, 16},{12, 17, 3},{-6, -8, -2}};rep(n, 13) rep(e, 3) coefs[n][e] = (mod + coefs[n][e]) % mod;const u32 N = 1000;rep(n, 13, N + 1) {u64 s = 0;rep(k, 13) {u64 m = n - k - 1;u64 t = (coefs[k][0] + m * coefs[k][1] + m * m % mod * coefs[k][2]) % mod;s = (s + t * terms[n - k - 1]) % mod;}s = u64(s) * inv4 % mod;terms.push_back(s);}u32 n;while (~scanf("%u", &n)) {printf("%u\n", terms[n]);}}int main() {clock_t beg = clock();solve();clock_t end = clock();fprintf(stderr, "%.3f sec\n", double(end - beg) / CLOCKS_PER_SEC);return 0;}