#602132 (C++17) No.1302 Random Tree Score

提出ソース
結果

問題	No.1302 Random Tree Score
ユーザー	SHIJOU
提出日時	2021-01-10 14:46:52
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	668 ms / 3,000 ms
コード長	16,955 bytes
コンパイル時間	3,462 ms
コンパイル使用メモリ	234,736 KB
実行使用メモリ	8,952 KB
最終ジャッジ日時	2024-11-21 00:24:18
合計ジャッジ時間	9,022 ms
ジャッジサーバーID （参考情報）	judge2 / judge3
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,820 KB
testcase_02	AC	123 ms 6,816 KB
testcase_03	AC	292 ms 6,816 KB
testcase_04	AC	120 ms 6,816 KB
testcase_05	AC	668 ms 8,492 KB
testcase_06	AC	562 ms 8,868 KB
testcase_07	AC	114 ms 6,816 KB
testcase_08	AC	328 ms 6,820 KB
testcase_09	AC	543 ms 8,952 KB
testcase_10	AC	560 ms 8,196 KB
testcase_11	AC	106 ms 6,820 KB
testcase_12	AC	619 ms 8,272 KB
testcase_13	AC	2 ms 6,816 KB
testcase_14	AC	542 ms 8,948 KB
testcase_15	AC	601 ms 8,568 KB
testcase_16	AC	2 ms 6,820 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = int64_t;
using ld = long double;
using P = pair<int, int>;
using vs = vector<string>;
using vi = vector<int>;
using vvi = vector<vi>;
template<class T> using PQ = priority_queue<T>;
template<class T> using PQG = priority_queue<T, vector<T>, greater<T> >;
const int INF = 0xccccccc;
const ll LINF = 0xcccccccccccccccLL;
template<typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) {return a < b && (a = b, true);}
template<typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) {return a > b && (a = b, true);}
template<typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) { return is >> p.first >> p.second;}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) { return os << p.first << ' ' << p.second;}

namespace fft {

constexpr unsigned int modulo = 998244353;
constexpr long double PI = 3.141592653589793238L;

struct modint_base {};
template<class C> using is_modint = is_base_of<modint_base, C>;
template<class C> using is_modint_t = enable_if_t<is_modint<C>::value>;
template<class C> using is_complex = typename conditional<is_same<C, complex<double>>::value || is_same<C, complex<long double>>::value, true_type, false_type>::type;

//begin NTT
template<int m>
struct mint : modint_base {
	unsigned int x;
	static constexpr int mod() {return m;}
	static constexpr unsigned int umod() {return m;}
	mint():x(0) {}
	mint(int64_t x_) {
		int64_t v = int64_t(x_ % umod());
		if(v < 0) v += umod();
		x = (unsigned int)v;
	}
	static mint row(int v) {
		mint v_;
		v_.x = v;
		return v_;
	}
	mint operator-() const { return mint(-int64_t(x));}
	mint& operator+=(const mint a) {
		if ((x += a.x) >= umod()) x -= umod();
		return *this;
	}
	mint& operator-=(const mint a) {
		if ((x += umod()-a.x) >= umod()) x -= umod();
		return *this;
	}
	mint& operator*=(const mint a) {
		uint64_t z = x;
		z *= a.x;
		x = (unsigned int)(z % umod());
		return *this;
	}
	mint operator+(const mint a) const { return mint(*this) += a;}
	mint operator-(const mint a) const { return mint(*this) -= a;}
	mint operator*(const mint a) const { return mint(*this) *= a;}
	mint &operator++() {
		x++;
		if(x == umod()) x = 0;
		return *this;
	}
	mint &operator--() {
		if(x == 0) x = umod();
		x--;
		return *this;
	}
	mint operator++(int) {
		mint result = *this;
		++*this;
		return result;
	}
	mint operator--(int) {
		mint result = *this;
		--*this;
		return result;
	}
	mint pow(int64_t t) const {
		mint x_ = *this, r = 1;
		while(t) {
			if(t&1) r *= x_;
			x_ *= x_;
			t >>= 1;
		}
		return r;
	}
	mint inv() const { return pow(umod()-2);}
	mint& operator/=(const mint a) { return *this *= a.inv();}
	mint operator/(const mint a) {return mint(*this) /= a;}
	friend bool operator==(const mint &a, const mint &b) {return a.x == b.x;}
	friend bool operator!=(const mint &a, const mint &b) {return a.x != b.x;}
	friend istream &operator>>(istream &is, mint &x) {return is >> x.x;}
	friend ostream &operator<<(ostream &os, const mint &x) {return os << x.x;}
};

constexpr int64_t safe_mod(int64_t x, int64_t m) {
	x %= m;
	if(x < 0) x += m;
	return x;
}

constexpr int64_t pow_mod_constexpr(int64_t x, int64_t n, int m) {
	if(m == 1) return 0;
	unsigned int _m = (unsigned int)(m);
	uint64_t r = 1;
	uint64_t y = safe_mod(x, m);
	while(n) {
		if(n&1) r = (r*y)%_m;
		y = (y*y)%_m;
		n >>= 1;
	}
	return r;
}

constexpr int primitive_root_constexpr(int m) {
	if(m == 2) return 1;
	if(m == 167772161) return 3;
	if(m == 469762049) return 3;
	if(m == 754974721) return 11;
	if(m == 998244353) return 3;
	int divs[20] = {};
	divs[0] = 2;
	int cnt = 1;
	int x = (m-1)>>1;
	while(~x&1) x >>= 1;
	for(int i = 3; (int64_t)(i)*i <= x; i += 2) {
		if(x%i == 0) {
			divs[cnt++] = i;
			while(x%i == 0) x /= i;
		}
	}
	if(x > 1) divs[cnt++] = x;
	for(int g = 2;; g++) {
		bool ok = true;
		for(int i = 0; i < cnt; i++) {
			if(pow_mod_constexpr(g, (m-1)/divs[i], m) == 1) {
				ok = false;
				break;
			}
		}
		if(ok) return g;
	}
}
template<int m> constexpr int primitive_root = primitive_root_constexpr(m);

constexpr pair<int64_t, int64_t> inv_gcd(int64_t a, int64_t b) {
	a = safe_mod(a, b);
	if(a == 0) return {b, 0};
	int64_t s = b, t = a;
	int64_t m0 = 0, m1 = 1;
	while(t) {
		int64_t u = s/t;
		s -= t*u;
		m0 -= m1*u;
		int64_t tmp = s;
		s = t;
		t = tmp;
		tmp = m0;
		m0 = m1;
		m1 = tmp;
	}
	if(m0 < 0) m0 += b/s;
	return {s, m0};
}

int ceil_pow2(int n) {
	int x = 0;
	while((1U << x) < (unsigned int)(n)) x++;
	return x;
}

template<class mint, is_modint_t<mint>* = nullptr>
void butterfly(vector<mint> &ary) {
	static constexpr int g = primitive_root<mint::mod()>;
	int n = int(ary.size());
	int h = ceil_pow2(n);

	static bool first = true;
	static mint sum_e[30];
	if(first) {
		first = false;
		mint es[30], ies[30];
		int cnt2 = __builtin_ctz(mint::mod()-1);
		mint e = mint(g).pow((mint::mod()-1)>>cnt2), ie = e.inv();
		for(int i = cnt2; i >= 2; i--) {
			es[i-2] = e;
			ies[i-2] = ie;
			e *= e;
			ie *= ie;
		}
		mint now(1);
		for(int i = 0; i <= cnt2-2; i++) {
			sum_e[i] = es[i] * now;
			now *= ies[i];
		}
	}
	for(int ph = 1; ph <= h; ph++) {
		int w = 1<<(ph-1), p = 1<<(h-ph);
		mint now(1);
		for(int s = 0; s < w; s++) {
			int offset = s << (h-ph+1);
			for(int i = 0; i < p; i++) {
				mint l = ary[i+offset];
				mint r = ary[i+offset+p] * now;
				ary[i+offset] = l+r;
				ary[i+offset+p] = l-r;
			}
			now *= sum_e[__builtin_ctz(~(unsigned int)(s))];
		}
	}
}

template<class mint, is_modint_t<mint>* = nullptr>
void butterfly_inv(vector<mint> &ary) {
	static constexpr int g = primitive_root<mint::mod()>;
	int n = int(ary.size());
	int h = ceil_pow2(n);

	static bool first = true;
	static mint sum_ie[30];
	if(first) {
		first = false;
		mint es[30], ies[30];
		int cnt2 = __builtin_ctz(mint::mod()-1);
		mint e = mint(g).pow((mint::mod()-1)>>cnt2), ie = e.inv();
		for(int i = cnt2; i >= 2; i--) {
			es[i-2] = e;
			ies[i-2] = ie;
			e *= e;
			ie *= ie;
		}
		mint now(1);
		for(int i = 0; i <= cnt2-2; i++) {
			sum_ie[i] = ies[i] * now;
			now *= es[i];
		}
	}
	for(int ph = h; ph >= 1; ph--) {
		int w = 1<<(ph-1), p = 1<<(h-ph);
		mint inow(1);
		for(int s = 0; s < w; s++) {
			int offset = s<<(h-ph+1);
			for(int i = 0; i < p; i++) {
				mint l = ary[i+offset];
				mint r = ary[i+offset+p];
				ary[i+offset] = l+r;
				ary[i+offset+p] = (uint64_t)(mint::mod() + l.x - r.x) * inow.x;
			}
			inow *= sum_ie[__builtin_ctz(~(unsigned int)(s))];
		}
	}
}

template<class mint, is_modint_t<mint>* = nullptr>
vector<mint> convolution(vector<mint> a, vector<mint> b) {
	int n = int(a.size()), m = int(b.size());
	if(!n || !m) return {};
	if(min(n, m) <= 60) {
		if(n < m) {
			swap(n, m);
			swap(a, b);
		}
		vector<mint> ans(n+m-1);
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++) {
				ans[i+j] += a[i] * b[j];
			}
		}
		return ans;
	}
	int z = 1<<ceil_pow2(n+m-1);
	a.resize(z);
	butterfly(a);
	b.resize(z);
	butterfly(b);
	for(int i = 0; i < z; i++) {
		a[i] *= b[i];
	}
	butterfly_inv(a);
	a.resize(n+m-1);
	mint iz = mint(z).inv();
	for(int i = 0; i < n+m-1; i++) a[i] *= iz;
	return a;
}

template<unsigned int mod = modulo, class T, enable_if_t<is_integral<T>::value>* = nullptr>
vector<T> convolution(const vector<T> &a, const vector<T> &b) {
	int n = int(a.size()), m = int(b.size());
	if(!n || !m) return {};

	using Mint = mint<mod>;
	vector<Mint> a2(n), b2(m);
	for(int i = 0; i < n; i++) {
		a2[i] = Mint(a[i]);
	}
	for(int i = 0; i < m; i++) {
		b2[i] = Mint(b[i]);
	}
	vector<Mint> c2 = convolution<Mint>(move(a2), move(b2));
	vector<T> c(n+m-1);
	for(int i = 0; i < n+m-1; i++) c[i] = c2[i].x;
	return c;
}

vector<int64_t> convolution_ll(const vector<int64_t> &a, vector<int64_t> &b) {
	int n = int(a.size()), m = int(b.size());
	if(!n || !m) return {};

	static constexpr uint64_t MOD1 = 754974721;  // 2^24
	static constexpr uint64_t MOD2 = 167772161;  // 2^25
	static constexpr uint64_t MOD3 = 469762049;  // 2^26
	static constexpr uint64_t M2M3 = MOD2 * MOD3;
	static constexpr uint64_t M1M3 = MOD1 * MOD3;
	static constexpr uint64_t M1M2 = MOD1 * MOD2;
	static constexpr uint64_t M1M2M3 = MOD1 * MOD2 * MOD3;

	static constexpr uint64_t i1 = inv_gcd(M2M3, MOD1).second;
	static constexpr uint64_t i2 = inv_gcd(M1M3, MOD2).second;
	static constexpr uint64_t i3 = inv_gcd(M1M2, MOD3).second;

	vector<int64_t> c1 = convolution<MOD1>(a, b);
	vector<int64_t> c2 = convolution<MOD2>(a, b);
	vector<int64_t> c3 = convolution<MOD3>(a, b);

	vector<int64_t> c(n+m-1);
	for(int i = 0; i < n+m-1; i++) {
		uint64_t x = 0;
		x += (c1[i] * i1) % MOD1 * M2M3;
		x += (c2[i] * i2) % MOD2 * M1M3;
		x += (c3[i] * i3) % MOD3 * M1M2;
		int64_t diff = c1[i] - safe_mod(int64_t(x), int64_t(MOD1));
		if(diff < 0) diff += MOD1;
		static constexpr uint64_t offset[5] = {0, 0, M1M2M3, 2*M1M2M3, 3*M1M2M3};
		x -= offset[diff%5];
		c[i] = x;
	}
	return c;
}

//begin FFT
template<class Float, enable_if_t<is_floating_point<Float>::value>* = nullptr>
void butterfly(vector<complex<Float>> &ary) {
	int n = int(ary.size());
	int h = ceil_pow2(n);

	using Complex = complex<Float>;
	static bool first = true;
	static Complex sum_e[30];
	if(first) {
		first = false;
		Complex now = 1.0;
		for(int i = 0; i < 28; i++) {
			Complex es = polar(Float(1.0), Float(PI)/(1<<(i+1)));
			sum_e[i] = es * now;
			now *= conj(es);
		}
	}
	for(int ph = 1; ph <= h; ph++) {
		int w = 1<<(ph-1), p = 1<<(h-ph);
		Complex now = Complex(1.0, 0);
		for(int s = 0; s < w; s++) {
			int offset = s<<(h-ph+1);
			for(int i = 0; i < p; i++) {
				Complex l = ary[i+offset];
				Complex r = ary[i+offset+p] * now;
				ary[i+offset] = l+r;
				ary[i+offset+p] = l-r;
			}
			now *= sum_e[__builtin_ctz(~(unsigned int)(s))];
		}
	}
}

template<class Float, enable_if_t<is_floating_point<Float>::value>* = nullptr>
void butterfly_inv(vector<complex<Float>> &ary) {
	int n = int(ary.size());
	int h = ceil_pow2(n);

	using Complex = complex<Float>;
	static bool first = true;
	static Complex sum_ie[30];
	if(first) {
		first = false;
		Complex now = 1.0;
		for(int i = 0; i < 28; i++) {
			Complex es = polar(Float(1.0), Float(PI)/(1<<(i+1)));
			sum_ie[i] = conj(es) * now;
			now *= es;
		}
	}
	for(int ph = h; ph >= 1; ph--) {
		int w = 1<<(ph-1), p = 1<<(h-ph);
		Complex inow = Complex(1.0, 0);
		for(int s = 0; s < w; s++) {
			int offset = s<<(h-ph+1);
			for(int i = 0; i < p; i++) {
				Complex l = ary[i+offset];
				Complex r = ary[i+offset+p];
				ary[i+offset] = l+r;
				ary[i+offset+p] = (l-r) * inow;
			}
			inow *= sum_ie[__builtin_ctz(~(unsigned int)(s))];
		}
	}
	Complex in(1.0/n, 0);
	for(int i = 0; i < n; i++) ary[i] *= in;
}

template<class Complex, enable_if_t<is_complex<Complex>::value>* = nullptr>
vector<Complex> convolution(vector<Complex> a, vector<Complex> b) {
	int n = int(a.size()), m = int(b.size());
	if(!n || !m) return {};
	if(min(n, m) <= 60) {
		if(n < m) {
			swap(n, m);
			swap(a, b);
		}
		vector<Complex> ans(n+m-1);
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++) {
				ans[i+j] += a[i] * b[j];
			}
		}
		return ans;
	}
	int z = 1<<ceil_pow2(n+m-1);
	a.resize(z);
	butterfly(a);
	b.resize(z);
	butterfly(b);
	for(int i = 0; i < z; i++) {
		a[i] *= b[i];
	}
	butterfly_inv(a);
	a.resize(n+m-1);
	return a;
}

template<class Float, enable_if_t<is_floating_point<Float>::value>* = nullptr>
vector<Float> convolution(vector<Float> &a, vector<Float> &b) {
	int n = int(a.size()), m = int(b.size());
	if(!n || !m) return {};

	using Complex = complex<Float>;
	vector<Complex> a2(n), b2(m);
	for(int i = 0; i < n; i++) a2[i] = Complex(a[i], 0);
	for(int i = 0; i < m; i++) b2[i] = Complex(b[i], 0);
	vector<Complex> c2 = convolution(move(a2), move(b2));
	vector<Float> c(n+m-1);
	for(int i = 0; i < n+m-1; i++) c[i] = c2[i].real();
	return c;
}

//modulo 998244353
//vector<mint<m>> convolution(vector<mint<m>>, vector<mint<m>>)
//vector<T> convolution<mod = modulo>(vector<T>&, vector<T>&) ##is_integral<T>::value == true
//vector<int64_t> convolution_ll(vector<int64_t>&, vector<int64_t>&)
//vector<Complex> convolution(vector<Complex>, vector<Complex>)
//vector<Float> convolution(vector<Float>&, vector<Float>&)

} // namespace fft

template<int m>
string to_string(fft::mint<m> a) {
	return to_string(a.x);
}

#define USE_NTT
//#define USE_ll_TYPE //(convolution_llの引数の参照を取る必要あり & 割り算無理)

template<class T>
struct FPS : vector<T> {
	using vector<T>::vector;
	using vector<T>::operator=;
	FPS operator-() const {
		int n = (*this).size();
		FPS res(n);
		for(int i = 0; i < n; i++) res[i] = -(*this)[i];
		return res;
	}
	FPS &operator+=(const FPS &a) {
		int n = (*this).size();
		int m = a.size();
		this->resize(max(n, m));
		for(int i = 0; i < m; i++) (*this)[i] += a[i];
		return *this;
	}
	FPS &operator-=(const FPS &a) {
		int n = (*this).size();
		int m = a.size();
		this->resize(max(n, m));
		for(int i = 0; i < m; i++) (*this)[i] -= a[i];
		return *this;
	}
#ifdef USE_NTT
	FPS &operator*=(const FPS &a) {
#ifdef USE_ll_TYPE
		*this = fft::convolution_ll(*this, a);
#else
		*this = fft::convolution(*this, a);
#endif
		return *this;
	}
	FPS &operator/=(const FPS &a) {
		int n = (*this).size();
		int m = a.size();
		*this = fft::convolution(*this, a.inv(max(n, m)));
		this->resize(n);
		return *this;
	}
	FPS inv(int d = -1) const {
		int n =(*this).size();
		assert(n > 0 and (*this)[0] != 0);
		if(d == -1) d = n;
		FPS res{T(1)/(*this)[0]};
		res.reserve(1<<fft::ceil_pow2(d));
		while(int(size(res)) < d) {
			int m = size(res);
			FPS x(begin(*this), begin(*this)+min(n, 2*m));
			FPS y = res;
			x.resize(2*m);
			y.resize(2*m);
			fft::butterfly(x);
			fft::butterfly(y);
			for(int i = 0; i < 2*m; i++) x[i] *= y[i];
			fft::butterfly_inv(x);
			T iz = T(1)/(2*m);
			for(auto &e:x) e *= iz;
			x.erase(begin(x), begin(x)+m);
			x.resize(2*m);
			fft::butterfly(x);
			for(int i = 0; i < 2*m; i++) x[i] *= -y[i];
			fft::butterfly_inv(x);
			for(auto &e:x) e *= iz;
			copy(begin(x), begin(x)+m, back_inserter(res));
		}
		res.resize(d);
		return res;
	}
#else
	FPS &operator*=(const FPS &a) {
		int n = (*this).size();
		int m = a.size();
		this->resize(n+m-1);
		for(int i = n+m-2; i >= 0; i--) {
			(*this)[i] *= a[0];
			for(int j = 1; j < min(i+1, m); j++) {
				(*this)[i] += (*this)[i-j] * a[j];
			}
		}
		return (*this);
	}
	FPS &operator/=(const FPS &a) {
		int n = (*this).size();
		int m = a.size();
		assert(a[0] != T(0));
		for(int i = 0; i < n; i++) {
			for(int j = 1; j < min(i+1, m); j++) {
				(*this)[i] -= (*this)[i-j] * a[j];
			}
			(*this)[i] /= a[0];
		}
		return *this;
	}
#endif
	FPS &operator<<=(int r) {
		(*this).insert(begin(*this), r, 0);
		return *this;
	}
	FPS &operator>>=(int r) {
		(*this).erase(begin(*this), begin(*this)+min(int((*this).size()), r));
		return *this;
	}
	friend FPS operator+(const FPS &lhs, const FPS &rhs) {
		return FPS(lhs) += rhs;
	}
	friend FPS operator-(const FPS &lhs, const FPS &rhs) {
		return FPS(lhs) -= rhs;
	}
	friend FPS operator*(const FPS &lhs, const FPS &rhs) {
		return FPS(lhs) *= rhs;
	}
	friend FPS operator/(const FPS &lhs, const FPS &rhs) {
		return FPS(lhs) /= rhs;
	}
	friend FPS operator<<(const FPS &lhs, const int rhs) {
		return FPS(lhs) <<= rhs;
	}
	friend FPS operator>>(const FPS &lhs, const int rhs) {
		return FPS(lhs) >>= rhs;
	}
	// g is considered to be sorted
	void mul(vector<pair<int, T>> g) {
		int n = (*this).size();
		int d;
		T c;
		tie(d, c) = g[0];
		if(d == 0) g.erase(g.begin());
		else c = 0;
		for(int i = n-1; i >= 0; i--) {
			(*this)[i] *= c;
			for(auto &p:g) {
				if(p.first > i) break;
				(*this)[i] += (*this)[i-p.first] * p.second;
			}
		}
	}
	void div(vector<pair<int, T>> g) {
		int n = (*this).size();
		int d;
		T c;
		tie(d, c) = g[0];
		assert(d == 0 and c != T(0));
		g.erase(g.begin());
		c = T(1)/c;
		for(int i = 0; i < n; i++) {
			for(auto p:g) {
				if(p.first > i) break;
				(*this)[i] -= (*this)[i-p.first] * p.second;
			}
			(*this)[i] *= c;
		}
	}
	void mul(int d, T c) { // *(1 + cx^d)
		int n = (*this).size();
		for(int i = n-1; i >= d; i--) {
			(*this)[i] += (*this)[i-d] * c;
		}
	}
	void div(int d, T c) { // /(1 + cx^d)
		int n = (*this).size();
		for(int i = 0; i < n-d; i++) {
			(*this)[i+d] -= (*this)[i] * c;
		}
	}
};

//head

template<class T>
FPS<T> pow(FPS<T> &a, int p) {
	int n = a.size();
	FPS<T> res(1, 1), r = a;
	while(p) {
		if(p&1) res *= r;
		r *= r;
		p >>= 1;
		res.resize(n);
		r.resize(n);
	}
	return res;
}

using Mint = fft::mint<fft::modulo>;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	FPS<Mint> v(n-1);
	iota(all(v), 1);
	Mint now(1);
	for(int i = 1; i < n-1; i++) {
		now *= i;
		v[i] /= now;
	}
	v = pow(v, n);
	cout << v[n-2]*now/Mint(n).pow(n-2) << endl;
}
yukicoder

結果

テストケース

ソースコード
