結果

問題 No.980 Fibonacci Convolution Hard
ユーザー 👑 はまやんはまやんはまやんはまやん
提出日時 2020-02-01 09:56:10
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
MLE  
実行時間 -
コード長 7,098 bytes
コンパイル時間 3,308 ms
コンパイル使用メモリ 240,096 KB
実行使用メモリ 814,612 KB
最終ジャッジ日時 2023-10-18 23:49:04
合計ジャッジ時間 11,250 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 MLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
template<typename T, T MOD = 1000000007>
struct Mint {
	static constexpr T mod = MOD;
	T v;
	Mint() :v(0) {}
	Mint(signed v) :v(v) {}
	Mint(long long t) { v = t % MOD; if (v < 0) v += MOD; }

	Mint pow(long long k) {
		Mint res(1), tmp(v);
		while (k) {
			if (k & 1) res *= tmp;
			tmp *= tmp;
			k >>= 1;
		}
		return res;
	}

	static Mint add_identity() { return Mint(0); }
	static Mint mul_identity() { return Mint(1); }

	Mint inv() { return pow(MOD - 2); }

	Mint& operator+=(Mint a) { v += a.v; if (v >= MOD)v -= MOD; return *this; }
	Mint& operator-=(Mint a) { v += MOD - a.v; if (v >= MOD)v -= MOD; return *this; }
	Mint& operator*=(Mint a) { v = 1LL * v * a.v % MOD; return *this; }
	Mint& operator/=(Mint a) { return (*this) *= a.inv(); }

	Mint operator+(Mint a) const { return Mint(v) += a; }
	Mint operator-(Mint a) const { return Mint(v) -= a; }
	Mint operator*(Mint a) const { return Mint(v) *= a; }
	Mint operator/(Mint a) const { return Mint(v) /= a; }

	Mint operator-() const { return v ? Mint(MOD - v) : Mint(v); }

	bool operator==(const Mint a)const { return v == a.v; }
	bool operator!=(const Mint a)const { return v != a.v; }
	bool operator <(const Mint a)const { return v < a.v; }

	static Mint comb(long long n, int k) {
		Mint num(1), dom(1);
		for (int i = 0; i < k; i++) {
			num *= Mint(n - i);
			dom *= Mint(i + 1);
		}
		return num / dom;
	}
};
template<typename T, T MOD> constexpr T Mint<T, MOD>::mod;
template<typename T, T MOD>
ostream& operator<<(ostream& os, Mint<T, MOD> m) { os << m.v; return os; }
constexpr int bmds(int x) {
	const int v[] = { 1012924417, 924844033, 998244353,
					 897581057, 645922817 };
	return v[x];
}
constexpr int brts(int x) {
	const int v[] = { 5, 5, 3, 3, 3 };
	return v[x];
}

template<int X>
struct NTT {
	static constexpr int md = bmds(X);
	static constexpr int rt = brts(X);
	using M = Mint<int, md>;
	vector< vector<M> > rts, rrts;

	void ensure_base(int n) {
		if ((int)rts.size() >= n) return;
		rts.resize(n); rrts.resize(n);
		for (int i = 1; i < n; i <<= 1) {
			if (!rts[i].empty()) continue;
			M w = M(rt).pow((md - 1) / (i << 1));
			M rw = w.inv();
			rts[i].resize(i); rrts[i].resize(i);
			rts[i][0] = M(1); rrts[i][0] = M(1);
			for (int k = 1; k < i; k++) {
				rts[i][k] = rts[i][k - 1] * w;
				rrts[i][k] = rrts[i][k - 1] * rw;
			}
		}
	}

	void ntt(vector<M>& as, bool f) {
		int n = as.size();
		assert((n & (n - 1)) == 0);
		ensure_base(n);

		for (int i = 0, j = 1; j + 1 < n; j++) {
			for (int k = n >> 1; k > (i ^= k); k >>= 1);
			if (i > j) swap(as[i], as[j]);
		}

		for (int i = 1; i < n; i <<= 1) {
			for (int j = 0; j < n; j += i * 2) {
				for (int k = 0; k < i; k++) {
					M z = as[i + j + k] * (f ? rrts[i][k] : rts[i][k]);
					as[i + j + k] = as[j + k] - z;
					as[j + k] += z;
				}
			}
		}

		if (f) {
			M tmp = M(n).inv();
			for (int i = 0; i < n; i++) as[i] *= tmp;
		}
	}

	vector<M> multiply(vector<M> as, vector<M> bs) {
		int need = as.size() + bs.size() - 1;
		int sz = 1;
		while (sz < need) sz <<= 1;
		as.resize(sz, M(0));
		bs.resize(sz, M(0));

		ntt(as, 0); ntt(bs, 0);
		for (int i = 0; i < sz; i++) as[i] *= bs[i];
		ntt(as, 1);

		as.resize(need);
		return as;
	}

	vector<int> multiply(vector<int> as, vector<int> bs) {
		vector<M> am(as.size()), bm(bs.size());
		for (int i = 0; i < (int)am.size(); i++) am[i] = M(as[i]);
		for (int i = 0; i < (int)bm.size(); i++) bm[i] = M(bs[i]);
		vector<M> cm = multiply(am, bm);
		vector<int> cs(cm.size());
		for (int i = 0; i < (int)cs.size(); i++) cs[i] = cm[i].v;
		return cs;
	}
};
template<int X> constexpr int NTT<X>::md;
template<int X> constexpr int NTT<X>::rt;
struct Garner {
	using ll = long long;
	static NTT<0> ntt0;
	static NTT<1> ntt1;
	static NTT<2> ntt2;

	static constexpr int pow(int a, int b, int md) {
		int res = 1;
		a = a % md;
		while (b) {
			if (b & 1) res = (ll)res * a % md;
			a = (ll)a * a % md;
			b >>= 1;
		}
		return res;
	}

	static constexpr int inv(int x, int md) {
		return pow(x, md - 2, md);
	}

	inline void garner(int& c0, int c1, int c2, int m01, int MOD) {
		static constexpr int r01 = inv(ntt0.md, ntt1.md);
		static constexpr int r02 = inv(ntt0.md, ntt2.md);
		static constexpr int r12 = inv(ntt1.md, ntt2.md);

		c1 = (ll)(c1 - c0) * r01 % ntt1.md;
		if (c1 < 0) c1 += ntt1.md;

		c2 = (ll)(c2 - c0) * r02 % ntt2.md;
		c2 = (ll)(c2 - c1) * r12 % ntt2.md;
		if (c2 < 0) c2 += ntt2.md;

		c0 %= MOD;
		c0 += (ll)c1 * ntt0.md % MOD;
		if (c0 >= MOD) c0 -= MOD;
		c0 += (ll)c2 * m01 % MOD;
		if (c0 >= MOD) c0 -= MOD;
	}

	inline void garner(vector< vector<int> >& cs, int MOD) {
		int m01 = (ll)ntt0.md * ntt1.md % MOD;
		int sz = cs[0].size();
		for (int i = 0; i < sz; i++) garner(cs[0][i], cs[1][i], cs[2][i], m01, MOD);
	}

	vector<int> multiply(vector<int> as, vector<int> bs, int MOD = 1000000007) {
		vector< vector<int> > cs(3);
		cs[0] = ntt0.multiply(as, bs);
		cs[1] = ntt1.multiply(as, bs);
		cs[2] = ntt2.multiply(as, bs);
		size_t sz = as.size() + bs.size() - 1;
		for (auto& v : cs) v.resize(sz);
		garner(cs, MOD);
		return cs[0];
	}
};
NTT<0> Garner::ntt0;
NTT<1> Garner::ntt1;
NTT<2> Garner::ntt2;
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     @hamayanhamayan0
　　　　／　　　＼　 　  |　|
　　　 /　　 /￣￣￣￣/　　|
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿
　 　　　＼/＿＿＿＿/　（u　⊃
---------------------------------------------------------------------------------------------------*/














int p, Q;
int mo = 1000000007;
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> p;

	Garner ntt;
	vector<int> v1(2010101, 0), v2(2010101, 0);

	v1[2] = 1;
	rep(i, 3, 2010101) v1[i] = (1LL * v1[i - 1] * p + v1[i - 2]) % 1000000007;
	rep(i, 0, 2010101) v2[i] = v1[i];
	
	auto v3 = ntt.multiply(v1, v2);

	cin >> Q;
	rep(_, 0, Q) {
		int q; cin >> q;
		printf("%d\n", v3[q]);
	}
}
0