結果
問題 |
No.980 Fibonacci Convolution Hard
|
ユーザー |
|
提出日時 | 2021-01-20 02:52:22 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 76 ms / 2,000 ms |
コード長 | 2,334 bytes |
コンパイル時間 | 195 ms |
コンパイル使用メモリ | 33,920 KB |
最終ジャッジ日時 | 2025-01-18 02:44:11 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:82:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 82 | scanf("%d%d\n", &p.n, &Q); | ~~~~~^~~~~~~~~~~~~~~~~~~~ main.cpp:94:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 94 | scanf("%d", &n); | ~~~~~^~~~~~~~~~
ソースコード
#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; }