結果

問題 No.1482 Swap Many Permutations
コンテスト
ユーザー nok0
提出日時 2021-03-04 12:02:28
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 268 ms / 2,000 ms
コード長 3,736 bytes
コンパイル時間 4,465 ms
コンパイル使用メモリ 266,164 KB
最終ジャッジ日時 2025-01-19 10:00:03
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#include <atcoder/all>
using namespace std;

using mint = atcoder::modint998244353;

const int CombMAX = 3000000;
std::vector<mint> fac(CombMAX + 1), finv(CombMAX + 1), inv(CombMAX + 1);

struct Combinationinit {
	Combinationinit() {
		const int MOD = mint::mod();
		fac[0] = fac[1] = 1;
		finv[0] = finv[1] = 1;
		inv[1] = 1;
		for(int i = 2; i <= CombMAX; i++) {
			fac[i] = fac[i - 1] * i;
			inv[i] = (mint)MOD - inv[MOD % i] * (MOD / i);
			finv[i] = finv[i - 1] * inv[i];
		}
	}
} Combinationinit_;

mint fast_mod_factorial(long long n) {
	if(n >= mint::mod()) return 0;
	const int d = 1 << 15;
	std::vector<mint> seq({1, d + 1});
	seq.reserve(d + 1);
	int sz = 1;
	while(sz < d) {
		std::vector<mint> aux(sz, 1), f(sz * 4), g(sz * 4);
		for(int i = 0; i <= sz; i++) {
			f[i] = finv[i] * finv[sz - i] * seq[i];
			if((sz + i & 1) and f[i] != 0) f[i] *= -1;
		}
		std::vector<mint> pf(f), as;
		as.emplace_back(sz + 1);
		as.emplace_back(mint(sz) / d);
		as.emplace_back(mint(sz) / d + sz + 1);
		for(int idx = 0; idx < 3; idx++) {
			for(int i = 0; i < sz * 4; i++) f[i] = pf[i];
			for(int i = 1; i < sz * 2 + 2; i++) g[i] = (as[idx] - (sz - i + 1)).inv();
			f = atcoder::convolution(f, g);
			f.resize(sz * 4);
			mint prod = 1;
			for(int i = 0; i <= sz; i++) prod *= as[idx] - i;
			for(int i = 0; i <= sz; i++) {
				f[sz + i + 1] *= prod;
				prod *= as[idx] + i + 1;
				prod /= as[idx] - (sz - i);
			}
			if(idx == 0)
				for(int i = 0; i < sz; i++) aux[i] = f[sz + i + 1];
			if(idx == 1)
				for(int i = 0; i <= sz; i++) seq[i] *= f[sz + i + 1];
			if(idx == 2)
				for(int i = 0; i < sz; i++) aux[i] *= f[sz + i + 1];
		}
		for(auto x : aux) seq.emplace_back(x);
		sz <<= 1;
	}
	mint res = 1;
	int l = min((long long)d, (n + 1) / d);
	for(int i = 0; i < l; i++) res *= seq[i];
	for(int i = l * d + 1; i <= n; i++) res *= i;
	return res;
}

int sum_pality;
int main() {
	int n, m;
	cin >> n >> m;

	const int s = m * (m - 1) / 2;

	//s_fac[0] = s!, s_fac[1] = (s-1)!,..,s_fac[n] = (s-n)!
	mint fac_s = 1;
	vector<mint> s_fac(n + 1), s_finv(n + 1);
	auto s_fac_init = [&]() {
		if(s <= 1000000) {
			fac_s = fac[s];
			for(int i = 0; i <= n; i++) {
				if(s - i < 0) s_finv[i] = 0;
				s_finv[i] = finv[s - i];
			}
			return;
		} else {
			fac_s = fast_mod_factorial(s);
			s_finv[0] = fac_s.inv();
			for(int i = 0; i < n; i++) s_finv[i + 1] = s_finv[i] * (s - i);
			return;
		}
	};

	vector<mint> even_even, even_odd, odd_odd;

	auto convolution_init = [&]() {
		vector<mint> odd(n + 1), even(n + 1);
		for(int i = 0; i < n + 1 and s - i >= 0; i++) {
			if(i % 2)
				odd[i] = finv[i] * s_finv[i];
			else
				even[i] = finv[i] * s_finv[i];
		}
		even_even = atcoder::convolution(even, even);
		even_odd = atcoder::convolution(even, odd);
		odd_odd = atcoder::convolution(odd, odd);
	};

	vector<int> quadratic_residue(m);
	auto quadratic_residue_init = [&]() {
		for(int i = 1; i < m; i++)
			quadratic_residue[(long long)i * i % m] = 1;
	};

	s_fac_init();
	convolution_init();
	quadratic_residue_init();

	vector<int> b(n), c(n);

	auto decode_inversion = [&](int b, int c) {
		if(m == 2) return b == 1;
		return !quadratic_residue[c];
	};

	auto solver = [&](int k) -> mint {
		if(k == 1) return 1;
		if(k == 2) {
			if(b[0] == b[1] and c[0] == c[1]) return 0;
			return m * (m - 1);
		}
		if(k % 2) {
			return even_odd[k] * fac[k] * fac_s * fac_s;
		} else {
			if(sum_pality % 2)
				return odd_odd[k] * fac[k] * fac_s * fac_s;
			else
				return even_even[k] * fac[k] * fac_s * fac_s;
		}
	};

	for(int i = 0; i < n; i++) cin >> b[i] >> c[i];

	for(int i = 1; i <= n; i++) {
		sum_pality += decode_inversion(b[i - 1], c[i - 1]);
		cout << solver(i).val() << '\n';
	}

	return 0;
}
0