結果
| 問題 | No.980 Fibonacci Convolution Hard |
| ユーザー |
 square1001
|
| 提出日時 | 2020-01-31 21:36:21 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 6,192 bytes |
| コンパイル時間 | 1,294 ms |
| コンパイル使用メモリ | 92,204 KB |
| 実行使用メモリ | 130,552 KB |
| 最終ジャッジ日時 | 2024-09-17 07:21:12 |
| 合計ジャッジ時間 | 10,956 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | RE * 16 TLE * 1 |
ソースコード
#ifndef CLASS_FAST_MODINT#define CLASS_FAST_MODINT#include <cstdint>using singlebit = uint32_t;using doublebit = uint64_t;static constexpr int digit_level = 8 * sizeof(singlebit);static constexpr singlebit find_inv(singlebit n, int d = 6, singlebit x = 1) {return d == 0 ? x : find_inv(n, d - 1, x * (2 - x * n));}template <singlebit mod> class fast_modint {// Fast Modulo Integer, Assertion: mod < 2^(bits of singlebit - 1) and mod is primeprivate:singlebit n;static constexpr singlebit r2 = (((doublebit(1) << digit_level) % mod) << digit_level) % mod;static constexpr singlebit ninv = singlebit(-1) * find_inv(mod);singlebit reduce(doublebit x) const {singlebit res = (x + doublebit(singlebit(x) * ninv) * mod) >> digit_level;return res < mod ? res : res - mod;}public:fast_modint() : n(0) {};fast_modint(singlebit n_) { n = reduce(doublebit(n_ % mod) * r2); };static constexpr singlebit get_mod() { return mod; }singlebit get() const { return reduce(n); }bool operator==(const fast_modint& x) const { return n == x.n; }bool operator!=(const fast_modint& x) const { return n != x.n; }fast_modint& operator+=(const fast_modint& x) { n += x.n; n -= (n < mod ? 0 : mod); return *this; }fast_modint& operator-=(const fast_modint& x) { n += mod - x.n; n -= (n < mod ? 0 : mod); return *this; }fast_modint& operator*=(const fast_modint& x) { n = reduce(doublebit(n) * x.n); return *this; }fast_modint operator+(const fast_modint& x) const { return fast_modint(*this) += x; }fast_modint operator-(const fast_modint& x) const { return fast_modint(*this) -= x; }fast_modint operator*(const fast_modint& x) const { return fast_modint(*this) *= x; }fast_modint inv() const { return binpow(mod - 2); }fast_modint binpow(singlebit b) const {fast_modint ans(1), cur(*this);while (b > 0) {if (b & 1) ans *= cur;cur *= cur;b >>= 1;}return ans;}};#endif // CLASS_FAST_MODINT#ifndef CLASS_POLYNOMIAL_NTT#define CLASS_POLYNOMIAL_NTT#include <vector>#include <algorithm>template<singlebit mod, singlebit depth, singlebit primroot>class polynomial_ntt {public:using modulo = fast_modint<mod>;static void fourier_transform(std::vector<modulo>& v, bool inverse) {std::size_t s = v.size();for (std::size_t i = 0, j = 1; j < s - 1; ++j) {for (std::size_t k = s >> 1; k > (i ^= k); k >>= 1);if (i < j) std::swap(v[i], v[j]);}std::size_t sc = 0, sz = 1;while (sz < s) sz *= 2, ++sc;modulo root = modulo(primroot).binpow((mod - 1) >> sc);std::vector<modulo> pw(s + 1); pw[0] = 1;for (std::size_t i = 1; i <= s; i++) pw[i] = pw[i - 1] * root;std::size_t qs = s;for (std::size_t b = 1; b < s; b <<= 1) {qs >>= 1;for (std::size_t i = 0; i < s; i += b * 2) {for (std::size_t j = i; j < i + b; ++j) {modulo delta = pw[(inverse ? b * 2 - j + i : j - i) * qs] * v[j + b];v[j + b] = v[j] - delta;v[j] += delta;}}}if (!inverse) return;modulo powinv = modulo((mod + 1) / 2).binpow(sc);for (std::size_t i = 0; i < s; ++i) {v[i] = v[i] * powinv;}}static std::vector<modulo> convolve(std::vector<modulo> v1, std::vector<modulo> v2) {std::size_t s1 = v1.size(), s2 = v2.size(), s = 1;while (s < s1 || s < s2) s *= 2;v1.resize(s * 2); fourier_transform(v1, false);v2.resize(s * 2); fourier_transform(v2, false);for (singlebit i = 0; i < s * 2; ++i) v1[i] *= v2[i];fourier_transform(v1, true);v1.resize(s1 + s2 - 1);return v1;}};#endif // CLASS_POLYNOMIAL_NTT#include <vector>#include <algorithm>using namespace std;using ntt1 = polynomial_ntt<469762049, 26, 3>; using modulo1 = ntt1::modulo;using ntt2 = polynomial_ntt<167772161, 25, 3>; using modulo2 = ntt2::modulo;using ntt3 = polynomial_ntt<998244353, 23, 3>; using modulo3 = ntt3::modulo;using modulo = fast_modint<1000000007>;const modulo2 inv21 = modulo2(modulo1::get_mod()).inv();const modulo3 inv31 = modulo3(modulo1::get_mod()).inv();const modulo3 inv32 = modulo3(modulo2::get_mod()).inv();const modulo1 inv1b = modulo1(modulo::get_mod()).inv();const modulo2 inv2b = modulo2(modulo::get_mod()).inv();const modulo3 inv3b = modulo3(modulo::get_mod()).inv();template<class modulox>std::vector<modulox> get_modvector(std::vector<modulo> v) {std::vector<modulox> ans(v.size());for (std::size_t i = 0; i < v.size(); ++i) {ans[i] = modulox(v[i].get());}return ans;}vector<modulo> convolve(vector<modulo> v1, vector<modulo> v2) {vector<modulo1> res1 = ntt1::convolve(get_modvector<modulo1>(v1), get_modvector<modulo1>(v2));vector<modulo2> res2 = ntt2::convolve(get_modvector<modulo2>(v1), get_modvector<modulo2>(v2));vector<modulo3> res3 = ntt3::convolve(get_modvector<modulo3>(v1), get_modvector<modulo3>(v2));vector<modulo> res(v1.size() + v2.size() - 1);for (int i = 0; i < v1.size() + v2.size() - 1; ++i) {modulo1 m1 = res1[i];modulo2 m2 = (res2[i] - m1.get()) * inv21;modulo3 m3 = ((res3[i] - m1.get()) * inv31 - m2.get()) * inv32;singlebit m4 = ((m1.get() + doublebit(m2.get()) * modulo1::get_mod()) % modulo::get_mod() + doublebit(m3.get()) * modulo1::get_mod() % modulo::get_mod() * modulo2::get_mod()) % modulo::get_mod();res[i] = m4;}return res;}#include <vector>#include <iostream>using namespace std;int main() {int N, P, Q;cin >> N >> P >> Q;vector<modulo> seq(2000001);seq[0] = 0;if (N >= 2) seq[1] = 1;for (int i = 2; i < N; ++i) {seq[i] = seq[i - 1] * P + seq[i - 2];}vector<modulo> ans = convolve(seq, seq);for (int i = 0; i < Q; ++i) {int x;cin >> x; x -= 2;cout << ans[i].get() << '\n';}return 0;}