結果

問題 No.1302 Random Tree Score
ユーザー leaf_1415leaf_1415
提出日時 2020-11-30 20:32:52
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 3,637 bytes
コンパイル時間 1,537 ms
コンパイル使用メモリ 108,612 KB
実行使用メモリ 21,916 KB
最終ジャッジ日時 2024-09-13 02:33:47
合計ジャッジ時間 12,346 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2,312 ms
21,916 KB
testcase_01 AC 2,209 ms
14,808 KB
testcase_02 TLE -
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 <iostream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <cassert>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <string>
#include <algorithm>
#include <utility>
#include <complex>
#define rep(x, s, t) for(llint (x) = (s); (x) <= (t); (x)++)
#define chmin(x, y) (x) = min((x), (y))
#define chmax(x, y) (x) = max((x), (y))
#define all(x) (x).begin(),(x).end()
#define inf 1e18

using namespace std;

typedef long long llint;
typedef long long ll;
typedef pair<llint, llint> P;

const ll mod = 998244353;

const int FACT_MAX = 200005;
llint fact[FACT_MAX], fact_inv[FACT_MAX];

llint modpow(llint a, llint n)
{
	if(n == 0) return 1;
	if(n % 2){
		return ((a%mod) * (modpow(a, n-1)%mod)) % mod;
	}
	else{
		return modpow((a*a)%mod, n/2) % mod;
	}
}

void make_fact()
{
	llint val = 1;
	fact[0] = 1;
	for(int i = 1; i < FACT_MAX; i++){
		val *= i;
		val %= mod;
		fact[i] = val;
	}
	fact_inv[FACT_MAX-1] = modpow(fact[FACT_MAX-1], mod-2);
	for(int i = FACT_MAX-2; i >= 0; i--){
		fact_inv[i] = fact_inv[i+1] * (i+1) % mod;
	}
}

llint modpow(llint a, llint n, llint mod)
{
	if(n == 0) return 1;
	if(n % 2){
		return ((a%mod) * (modpow(a, n-1, mod)%mod)) % mod;
	}
	else{
		return modpow((a*a)%mod, n/2, mod) % mod;
	}
}

int rev(int x, int n)
{
	int ret = 0;
	for(int i = 0; i < n; i++){
		ret <<= 1;
		ret |= (x>>i) & 1;
	}
	return ret;
}

//f[]とF[]は異なる実体を持たなければならない。rootには1の原始2^n乗根を渡す
void DFT(llint f[], llint F[], int n, llint mod, llint root)
{
	int N = 1<<n;
	for(int i = 0; i < N; i++) F[rev(i, n)] = f[i];
	
	llint a, b, x, z;
	for(int i = 1; i <= n; i++){
		int l = 1<<i;
		z = modpow(root, 1<<(n-i), mod);
		for(int j = 0; j < N/l; j++){
			x = 1;
			for(int k = 0; k < l/2; k++){
				a = F[j*l+k], b = F[j*l+k+l/2];
				F[j*l+k] = a + x * b % mod;
				F[j*l+k+l/2] = a - x * b % mod + mod;
				if(F[j*l+k] >= mod) F[j*l+k] -= mod;
				if(F[j*l+k+l/2] >= mod) F[j*l+k+l/2] -= mod;
				x *= z, x %= mod;
			}
		}
	}
}

//f[]とF[]は異なる実体を持たなければならない。rootには1の原始2^n乗根を渡す
void IDFT(llint F[], llint f[], int n, llint mod, llint root)
{
	int N = 1<<n;
	for(int i = 0; i < N; i++) f[rev(i, n)] = F[i];
	root = modpow(root, mod-2, mod);
	
	llint a, b, x, z;
	for(int i = 1; i <= n; i++){
		int l = 1<<i;
		z = modpow(root, 1<<(n-i), mod);
		for(int j = 0; j < N/l; j++){
			x = 1;
			for(int k = 0; k < l/2; k++){
				a = f[j*l+k], b = f[j*l+k+l/2];
				f[j*l+k] = a + x * b % mod;
				f[j*l+k+l/2] = a - x * b % mod + mod;
				if(f[j*l+k] >= mod) f[j*l+k] -= mod;
				if(f[j*l+k+l/2] >= mod) f[j*l+k+l/2] -= mod;
				x *= z, x %= mod;
			}
		}
	}
	llint Ninv = modpow(N, mod-2, mod);
	for(int i = 0; i < N; i++) f[i] *= Ninv, f[i] %= mod;
}

ll n;
ll a[1<<18], A[1<<18];
ll b[1<<18], B[1<<18];
ll root;

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	make_fact();
	root = modpow(3, 119*32);
	
	cin >> n;
	rep(i, 0, n) a[i] = (i+1) * fact_inv[i] % mod;
	DFT(a, A, 18, mod, root);
	
	b[0] = 1;
	for(int i = 16; i >= 0; i--){
		DFT(b, B, 18, mod, root);
		rep(j, 0, (1<<18)-1) B[j] *= B[j], B[j] %= mod;
		IDFT(B, b, 18, mod, root);
		rep(j, n+1, (1<<18)-1) b[j] = 0;
		if(n & (1<<i)){
			DFT(b, B, 18, mod, root);
			rep(j, 0, (1<<18)-1) B[j] *= A[j], B[j] %= mod;
			IDFT(B, b, 18, mod, root);
			rep(j, n+1, (1<<18)-1) b[j] = 0;
		}
	}
	
	ll ans = b[n-2];
	ans *= fact[n-2], ans %= mod;
	ans *= modpow(modpow(n, n-2), mod-2), ans %= mod;
	cout << ans << endl;
	
	return 0;
}
0