#424729 (C++17) No.980 Fibonacci Convolution Hard

提出ソース
結果

問題	No.980 Fibonacci Convolution Hard
ユーザー	はまやんはまやん
提出日時	2020-02-01 10:29:53
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	1,015 ms / 2,000 ms
コード長	13,462 bytes
コンパイル時間	2,738 ms
コンパイル使用メモリ	222,460 KB
実行使用メモリ	75,992 KB
最終ジャッジ日時	2024-09-18 19:48:03
合計ジャッジ時間	22,931 ms
ジャッジサーバーID （参考情報）	judge1 / judge5
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	973 ms 75,784 KB
testcase_01	AC	975 ms 75,856 KB
testcase_02	AC	970 ms 75,820 KB
testcase_03	AC	987 ms 75,932 KB
testcase_04	AC	968 ms 75,808 KB
testcase_05	AC	966 ms 75,764 KB
testcase_06	AC	993 ms 75,992 KB
testcase_07	AC	983 ms 75,864 KB
testcase_08	AC	984 ms 75,780 KB
testcase_09	AC	979 ms 75,828 KB
testcase_10	AC	1,015 ms 75,776 KB
testcase_11	AC	983 ms 75,792 KB
testcase_12	AC	1,014 ms 75,820 KB
testcase_13	AC	989 ms 75,824 KB
testcase_14	AC	967 ms 75,868 KB
testcase_15	AC	960 ms 75,808 KB
testcase_16	AC	953 ms 75,896 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#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; }
//---------------------------------------------------------------------------------------------------
#ifdef _MSC_VER
#pragma push_macro("long")
#undef long
#ifdef _WIN32
inline unsigned int __builtin_ctz(unsigned int x) { unsigned long r; _BitScanForward(&r, x); return r; }
inline unsigned int __builtin_clz(unsigned int x) { unsigned long r; _BitScanReverse(&r, x); return 31 - r; }
inline unsigned int __builtin_ffs(unsigned int x) { unsigned long r; return _BitScanForward(&r, x) ? r + 1 : 0; }
inline unsigned int __builtin_popcount(unsigned int x) { return __popcnt(x); }
inline unsigned int __lg(int __n) { return sizeof(int) * 8 - 1 - __builtin_clz(__n); }
#ifdef _WIN64
inline unsigned long long __builtin_ctzll(unsigned long long x) { unsigned long r; _BitScanForward64(&r, x); return r; }
inline unsigned long long __builtin_clzll(unsigned long long x) { unsigned long r; _BitScanReverse64(&r, x); return 63 - r; }
inline unsigned long long __builtin_ffsll(unsigned long long x) { unsigned long r; return _BitScanForward64(&r, x) ? r + 1 : 0; }
inline unsigned long long __builtin_popcountll(unsigned long long x) { return __popcnt64(x); }
#else
inline unsigned int hidword(unsigned long long x) { return static_cast<unsigned int>(x >> 32); }
inline unsigned int lodword(unsigned long long x) { return static_cast<unsigned int>(x & 0xFFFFFFFF); }
inline unsigned long long __builtin_ctzll(unsigned long long x) { return lodword(x) ? __builtin_ctz(lodword(x)) : __builtin_ctz(hidword(x)) + 32; }
inline unsigned long long __builtin_clzll(unsigned long long x) { return hidword(x) ? __builtin_clz(hidword(x)) : __builtin_clz(lodword(x)) + 32; }
inline unsigned long long __builtin_ffsll(unsigned long long x) { return lodword(x) ? __builtin_ffs(lodword(x)) : hidword(x) ? __builtin_ffs(hidword(x)) + 32 : 0; }
inline unsigned long long __builtin_popcountll(unsigned long long x) { return __builtin_popcount(lodword(x)) + __builtin_popcount(hidword(x)); }
#endif // _WIN64
#endif // _WIN32
#pragma pop_macro("long")
#endif // _MSC_VER
template<class t> using vc = vector<t>;
template<class t> using vvc = vc<vc<t>>;

using pi = pair<int, int>;
using vi = vc<int>;
using uint = unsigned;
using ull = unsigned long long;
#define si(x) int(x.size())

struct modinfo { uint mod, root; };
template<modinfo const& ref>
struct modular {
	static constexpr uint const& mod = ref.mod;
	static modular root() { return modular(ref.root); }
	uint v;
	//modular(initializer_list<uint>ls):v(*ls.bg){}
	modular(ll vv = 0) { s(vv % mod + mod); }
	modular& s(uint vv) {
		v = vv < mod ? vv : vv - mod;
		return *this;
	}
	modular operator-()const { return modular() - *this; }
	modular& operator+=(const modular& rhs) { return s(v + rhs.v); }
	modular& operator-=(const modular& rhs) { return s(v + mod - rhs.v); }
	modular& operator*=(const modular& rhs) {
		v = ull(v) * rhs.v % mod;
		return *this;
	}
	modular& operator/=(const modular& rhs) { return *this *= rhs.inv(); }
	modular operator+(const modular& rhs)const { return modular(*this) += rhs; }
	modular operator-(const modular& rhs)const { return modular(*this) -= rhs; }
	modular operator*(const modular& rhs)const { return modular(*this) *= rhs; }
	modular operator/(const modular& rhs)const { return modular(*this) /= rhs; }
	modular pow(int n)const {
		modular res(1), x(*this);
		while (n) {
			if (n & 1)res *= x;
			x *= x;
			n >>= 1;
		}
		return res;
	}
	modular inv()const { return pow(mod - 2); }
	/*modular inv()const{
		int x,y;
		int g=extgcd(v,mod,x,y);
		assert(g==1);
		if(x<0)x+=mod;
		return modular(x);
	}*/
	friend modular operator+(int x, const modular& y) {
		return modular(x) + y;
	}
	friend modular operator-(int x, const modular& y) {
		return modular(x) - y;
	}
	friend modular operator*(int x, const modular& y) {
		return modular(x) * y;
	}
	friend modular operator/(int x, const modular& y) {
		return modular(x) / y;
	}
	friend ostream& operator<<(ostream& os, const modular& m) {
		return os << m.v;
	}
	friend istream& operator>>(istream& is, modular& m) {
		ll x; is >> x;
		m = modular(x);
		return is;
	}
	bool operator<(const modular& r)const { return v < r.v; }
	bool operator==(const modular& r)const { return v == r.v; }
	bool operator!=(const modular& r)const { return v != r.v; }
	explicit operator bool()const {
		return v;
	}
};

#define USE_FMT

/*
//998244353
const mint prim_root=3;
//in-place fft
//size of input must be a power of 2
void inplace_fmt(vector<mint>&f,const bool inv){
	const int n=f.size();
	const mint root=inv?prim_root.inv():prim_root;
	vc<mint> g(n);
	for(int b=n/2;b>=1;b/=2){
		mint w=root.pow((mint::base-1)/(n/b)),p=1;
		for(int i=0;i<n;i+=b*2){
			rep(j,b){
				f[i+j+b]*=p;
				g[i/2+j]=f[i+j]+f[i+b+j];
				g[n/2+i/2+j]=f[i+j]-f[i+b+j];
			}
			p*=w;
		}
		swap(f,g);
	}
	if(inv)rep(i,n)
		f[i]*=inv[n];
}*/

//size of input must be a power of 2
//output of forward fmt is bit-reversed
//output elements are in the range [0,mod*4)
//input of inverse fmt should be bit-reversed
template<class mint>
void inplace_fmt(const int n, mint* const f, bool inv) {
	static constexpr uint mod = mint::mod;
	static constexpr uint mod2 = mod * 2;
	static const int L = 30;
	static mint g[L], ig[L], p2[L];
	if (g[0].v == 0) {
		rep(i, 0, L) {
			mint w = -mint::root().pow(((mod - 1) >> (i + 2)) * 3);
			g[i] = w;
			ig[i] = w.inv();
			p2[i] = mint(1 << i).inv();
		}
	}
	if (!inv) {
		int b = n;
		if (b >>= 1) {//input:[0,mod)
			rep(i, 0, b) {
				uint x = f[i + b].v;
				f[i + b].v = f[i].v + mod - x;
				f[i].v += x;
			}
		}
		if (b >>= 1) {//input:[0,mod*2)
			mint p = 1;
			for (int i = 0, k = 0; i < n; i += b * 2) {
				rep(j, i, i + b) {
					uint x = (f[j + b] * p).v;
					f[j + b].v = f[j].v + mod - x;
					f[j].v += x;
				}
				p *= g[__builtin_ctz(++k)];
			}
		}
		while (b) {
			if (b >>= 1) {//input:[0,mod*3)
				mint p = 1;
				for (int i = 0, k = 0; i < n; i += b * 2) {
					rep(j, i, i + b) {
						uint x = (f[j + b] * p).v;
						f[j + b].v = f[j].v + mod - x;
						f[j].v += x;
					}
					p *= g[__builtin_ctz(++k)];
				}
			}
			if (b >>= 1) {//input:[0,mod*4)
				mint p = 1;
				for (int i = 0, k = 0; i < n; i += b * 2) {
					rep(j, i, i + b) {
						uint x = (f[j + b] * p).v;
						f[j].v = (f[j].v < mod2 ? f[j].v : f[j].v - mod2);
						f[j + b].v = f[j].v + mod - x;
						f[j].v += x;
					}
					p *= g[__builtin_ctz(++k)];
				}
			}
		}
	}
	else {
		int b = 1;
		if (b < n / 2) {//input:[0,mod)
			mint p = 1;
			for (int i = 0, k = 0; i < n; i += b * 2) {
				rep(j, i, i + b) {
					ull x = f[j].v + mod - f[j + b].v;
					f[j].v += f[j + b].v;
					f[j + b].v = x * p.v % mod;
				}
				p *= ig[__builtin_ctz(++k)];
			}
			b <<= 1;
		}
		for (; b < n / 2; b <<= 1) {
			mint p = 1;
			for (int i = 0, k = 0; i < n; i += b * 2) {
				rep(j, i, i + b / 2) {//input:[0,mod*2)
					ull x = f[j].v + mod2 - f[j + b].v;
					f[j].v += f[j + b].v;
					f[j].v = (f[j].v) < mod2 ? f[j].v : f[j].v - mod2;
					f[j + b].v = x * p.v % mod;
				}
				rep(j, i + b / 2, i + b) {//input:[0,mod)
					ull x = f[j].v + mod - f[j + b].v;
					f[j].v += f[j + b].v;
					f[j + b].v = x * p.v % mod;
				}
				p *= ig[__builtin_ctz(++k)];
			}
		}
		if (b < n) {//input:[0,mod*2)
			rep(i, 0, b) {
				uint x = f[i + b].v;
				f[i + b].v = f[i].v + mod2 - x;
				f[i].v += x;
			}
		}
		mint z = p2[__lg(n)];
		rep(i, 0, n)f[i] *= z;
	}
}

template<class mint>
void inplace_fmt(vector<mint>& f, bool inv) {
	inplace_fmt(si(f), f.data(), inv);
}

template<class mint>
void half_fmt(const int n, mint* const f) {
	static constexpr uint mod = mint::mod;
	static constexpr uint mod2 = mod * 2;
	static const int L = 30;
	static mint g[L], h[L];
	if (g[0].v == 0) {
		rep(i, 0, L) {
			g[i] = -mint::root().pow(((mod - 1) >> (i + 2)) * 3);
			h[i] = mint::root().pow((mod - 1) >> (i + 2));
		}
	}
	int b = n;
	int lv = 0;
	if (b >>= 1) {//input:[0,mod)
		mint p = h[lv++];
		for (int i = 0, k = 0; i < n; i += b * 2) {
			rep(j, i, i + b) {
				uint x = (f[j + b] * p).v;
				f[j + b].v = f[j].v + mod - x;
				f[j].v += x;
			}
			p *= g[__builtin_ctz(++k)];
		}
	}
	if (b >>= 1) {//input:[0,mod*2)
		mint p = h[lv++];
		for (int i = 0, k = 0; i < n; i += b * 2) {
			rep(j, i, i + b) {
				uint x = (f[j + b] * p).v;
				f[j + b].v = f[j].v + mod - x;
				f[j].v += x;
			}
			p *= g[__builtin_ctz(++k)];
		}
	}
	while (b) {
		if (b >>= 1) {//input:[0,mod*3)
			mint p = h[lv++];
			for (int i = 0, k = 0; i < n; i += b * 2) {
				rep(j, i, i + b) {
					uint x = (f[j + b] * p).v;
					f[j + b].v = f[j].v + mod - x;
					f[j].v += x;
				}
				p *= g[__builtin_ctz(++k)];
			}
		}
		if (b >>= 1) {//input:[0,mod*4)
			mint p = h[lv++];
			for (int i = 0, k = 0; i < n; i += b * 2) {
				rep(j, i, i + b) {
					uint x = (f[j + b] * p).v;
					f[j].v = (f[j].v < mod2 ? f[j].v : f[j].v - mod2);
					f[j + b].v = f[j].v + mod - x;
					f[j].v += x;
				}
				p *= g[__builtin_ctz(++k)];
			}
		}
	}
}

template<class mint>
void half_fmt(vector<mint>& f) {
	half_fmt(si(f), f.data());
}

/*
template<class mint>
vc<mint> multiply(vc<mint> x,const vc<mint>&y,bool same=false){
	int n=si(x)+si(y)-1;
	int s=1;
	while(s<n)s*=2;
	x.resize(s);inplace_fmt(x,false);
	if(!same){
		vc<mint> z(s);
		rep(i,si(y))z[i]=y[i];
		inplace_fmt(z,false);
		rep(i,s)x[i]*=z[i];
	}else{
		rep(i,s)x[i]*=x[i];
	}
	inplace_fmt(x,true);x.resize(n);
	return x;
}*/

//59501818244292734739283969-1=5.95*10^25 までの値を正しく計算
//最終的な列の大きさが 2^24 までなら動く
//最終的な列の大きさが 2^20 以下のときは，下の 3 つの素数を使ったほうが速い（は？）
//VERIFY: yosupo
namespace arbitrary_convolution {
	constexpr modinfo base0{ 167772161,3 };//2^25 * 5 + 1
	constexpr modinfo base1{ 469762049,3 };//2^26 * 7 + 1
	constexpr modinfo base2{ 754974721,11 };//2^24 * 45 + 1
	//constexpr modinfo base0{1045430273,3};//2^20 * 997 + 1
	//constexpr modinfo base1{1051721729,6};//2^20 * 1003 + 1
	//constexpr modinfo base2{1053818881,7};//2^20 * 1005 + 1
	using mint0 = modular<base0>;
	using mint1 = modular<base1>;
	using mint2 = modular<base2>;
	template<class t, class mint>
	vc<t> sub(const vc<mint>& x, const vc<mint>& y, bool same = false) {
		int n = si(x) + si(y) - 1;
		int s = 1;
		while (s < n)s *= 2;
		vc<t> z(s); rep(i, 0, si(x))z[i] = x[i].v;
		inplace_fmt(z, false);
		if (!same) {
			vc<t> w(s); rep(i, 0, si(y))w[i] = y[i].v;
			inplace_fmt(w, false);
			rep(i, 0, s)z[i] *= w[i];
		}
		else {
			rep(i, 0, s)z[i] *= z[i];
		}
		inplace_fmt(z, true); z.resize(n);
		return z;
	}
	constexpr modinfo base{ 1000000007,0 };
	using mint = modular<base>;
	vc<mint> multiply(const vc<mint>& x, const vc<mint>& y, bool same = false) {
		auto d0 = sub<mint0>(x, y, same);
		auto d1 = sub<mint1>(x, y, same);
		auto d2 = sub<mint2>(x, y, same);
		int n = si(d0);
		vc<mint> res(n);
		static const mint1 r01 = mint1(mint0::mod).inv();
		static const mint2 r02 = mint2(mint0::mod).inv();
		static const mint2 r12 = mint2(mint1::mod).inv();
		static const mint2 r02r12 = r02 * r12;
		static const mint w1 = mint(mint0::mod);
		static const mint w2 = w1 * mint(mint1::mod);
		rep(i, 0, n) {
			ull a = d0[i].v;
			ull b = (d1[i].v + mint1::mod - a) * r01.v % mint1::mod;
			ull c = ((d2[i].v + mint2::mod - a) * r02r12.v + (mint2::mod - b) * r12.v) % mint2::mod;
			res[i].v = (a + b * w1.v + c * w2.v) % mint::mod;
		}
		return res;
	}
}
using arbitrary_convolution::multiply;
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     @hamayanhamayan0
　　　　／　　　＼　 　  |　|
　　　 /　　 /￣￣￣￣/　　|
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿
　 　　　＼/＿＿＿＿/　（u　⊃
---------------------------------------------------------------------------------------------------*/














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

	vector<arbitrary_convolution::mint> v(ma, 0);

	v[2] = 1;
	rep(i, 3, ma) v[i] = (v[i - 1] * p + v[i - 2]);
	
	auto ans = multiply(v, v, true);

	cin >> Q;
	rep(_, 0, Q) {
		int q; cin >> q;
		printf("%u\n", ans[q].v);
	}
}
yukicoder

結果

テストケース

ソースコード
