結果
問題 | No.980 Fibonacci Convolution Hard |
ユーザー | Ryuhei Mori |
提出日時 | 2021-01-20 02:49:22 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 75 ms / 2,000 ms |
コード長 | 2,785 bytes |
コンパイル時間 | 276 ms |
コンパイル使用メモリ | 38,528 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-05-10 03:56:10 |
合計ジャッジ時間 | 5,277 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 74 ms
5,248 KB |
testcase_01 | AC | 74 ms
5,376 KB |
testcase_02 | AC | 74 ms
5,376 KB |
testcase_03 | AC | 74 ms
5,376 KB |
testcase_04 | AC | 75 ms
5,376 KB |
testcase_05 | AC | 74 ms
5,376 KB |
testcase_06 | AC | 74 ms
5,376 KB |
testcase_07 | AC | 75 ms
5,376 KB |
testcase_08 | AC | 74 ms
5,376 KB |
testcase_09 | AC | 74 ms
5,376 KB |
testcase_10 | AC | 74 ms
5,376 KB |
testcase_11 | AC | 73 ms
5,376 KB |
testcase_12 | AC | 73 ms
5,376 KB |
testcase_13 | AC | 74 ms
5,376 KB |
testcase_14 | AC | 74 ms
5,376 KB |
testcase_15 | AC | 74 ms
5,376 KB |
testcase_16 | AC | 57 ms
5,376 KB |
ソースコード
#include <cstdio> #include <utility> using u32 = unsigned int; using u64 = unsigned long long; template <u32 MOD> struct Mint { u32 n; constexpr Mint(u32 n = 0): n(n) {} constexpr Mint operator-() const { return Mint(n ? MOD - n: 0); } constexpr Mint &operator+=(const Mint &rhs){ n += rhs.n; if(n >= MOD) n -= MOD; return *this; } constexpr Mint &operator-=(const Mint &rhs){ if(rhs.n > n) n += MOD; n -= rhs.n; return *this; } constexpr Mint &operator*=(const Mint &rhs){ n = (u64) n * rhs.n % MOD; return *this; } friend constexpr Mint operator+(const Mint &lhs, const Mint &rhs){ return Mint(lhs) += rhs; } friend constexpr Mint operator-(const Mint &lhs, const Mint &rhs){ return Mint(lhs) -= rhs; } friend constexpr Mint operator*(const Mint &lhs, const Mint &rhs){ return Mint(lhs) *= rhs; } friend constexpr bool operator==(const Mint &lhs, const Mint &rhs){ return lhs.n == rhs.n; } friend constexpr bool operator!=(const Mint &lhs, const Mint &rhs){ return lhs.n != rhs.n; } }; template <class T> T mypow(T a, u32 n){ T r = 1; for(; n; n >>= 1){ if(n&1) r *= a; a *= a; } return r; } template <u32 MOD> Mint<MOD> inv(Mint<MOD> a){ return mypow(a, MOD-2); } constexpr u32 mod = 1000000007; using mint = Mint<mod>; mint p; /* x / (1 - px - x^2) 1 - (2 + p^2) x + x^2 0 1 p p^2+1 -p / (p^2 + 4) 0 1 2p 3(p^2+1) -p / (p^2 + 4) 1 p p^2+1 p^3+2p 0 p 2(p^2+1) 3(p^3+2p) 2 / (p^2 + 4) 0 0 1 2p */ mint q[21]; std::pair<mint, mint> bostan_mori_msb(u64 n){ mint a = 0, b = 1; for(int i = 63 - __builtin_clzll(n); i; i--){ if(n & (1 << i)){ a += b; b *= q[i]; } else { b += a; a *= q[i]; } } if(n & 1){ a = b - a; b *= q[0]; } else { b = b - a; a *= q[0]; } return {a, b}; } int main(){ u32 Q; scanf("%d%d\n", &p.n, &Q); for(int i = 1; i < 1000; i++) if(mint(i) * inv(mint(i)) != 1) puts("ERR"); /* mint f0[4], f1[4], f0n[4], f1n[4]; f0[0] = 0, f0[1] = 1; for(int i = 2; i < 4; i++) f0[i] = p * f0[i-1] + f0[i-2]; f1[0] = 0; for(int i = 1; i < 4; i++) f1[i] = f0[i-1]; for(int i = 0; i < 4; i++){ f0n[i] = i * f0[i]; f1n[i] = i * f1[i]; } mint g[4]; for(int i = 0; i < 4; i++){ g[i] = 0; for(int j = 0; j <= i; j++) g[i] += f0[j] * f0[i-j]; } */ mint s = inv(p * p + 4); mint t = 2 * s; s *= -p; q[0] = p; q[1] = p * p + 2; for(u32 i = 2; i < sizeof(q)/sizeof(*q); i++) q[i] = q[i-1] * q[i-1] - 2; while(Q--){ u32 n; scanf("%d", &n); n -= 2; auto [a, b] = bostan_mori_msb(n); mint z = s * (1 + n) * a + t * n * b; // printf("%d %d %d\n", a.n, b.n, z.n); printf("%d\n", z.n); } return 0; }