結果
問題 | No.980 Fibonacci Convolution Hard |
ユーザー | Ryuhei Mori |
提出日時 | 2021-01-20 02:52:22 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 78 ms / 2,000 ms |
コード長 | 2,334 bytes |
コンパイル時間 | 945 ms |
コンパイル使用メモリ | 38,272 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-05-10 03:59:20 |
合計ジャッジ時間 | 4,822 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 76 ms
5,248 KB |
testcase_01 | AC | 75 ms
5,376 KB |
testcase_02 | AC | 76 ms
5,376 KB |
testcase_03 | AC | 75 ms
5,376 KB |
testcase_04 | AC | 77 ms
5,376 KB |
testcase_05 | AC | 76 ms
5,376 KB |
testcase_06 | AC | 76 ms
5,376 KB |
testcase_07 | AC | 76 ms
5,376 KB |
testcase_08 | AC | 76 ms
5,376 KB |
testcase_09 | AC | 77 ms
5,376 KB |
testcase_10 | AC | 77 ms
5,376 KB |
testcase_11 | AC | 77 ms
5,376 KB |
testcase_12 | AC | 78 ms
5,376 KB |
testcase_13 | AC | 78 ms
5,376 KB |
testcase_14 | AC | 77 ms
5,376 KB |
testcase_15 | AC | 77 ms
5,376 KB |
testcase_16 | AC | 62 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 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); 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; }