#624903 (C++17) No.1482 Swap Many Permutations

提出ソース

結果

問題	No.1482 Swap Many Permutations
ユーザー	nok0
提出日時	2021-03-04 12:02:28
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	237 ms / 2,000 ms
コード長	3,736 bytes
コンパイル時間	5,126 ms
コンパイル使用メモリ	277,448 KB
実行使用メモリ	45,180 KB
最終ジャッジ日時	2024-10-04 17:00:56
合計ジャッジ時間	13,740 ms
ジャッジサーバーID （参考情報）	judge2 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	50 ms 38,376 KB
testcase_01	AC	51 ms 38,392 KB
testcase_02	AC	49 ms 38,472 KB
testcase_03	AC	53 ms 38,388 KB
testcase_04	AC	49 ms 38,544 KB
testcase_05	AC	49 ms 38,424 KB
testcase_06	AC	49 ms 38,320 KB
testcase_07	AC	73 ms 38,392 KB
testcase_08	AC	49 ms 38,372 KB
testcase_09	AC	49 ms 38,492 KB
testcase_10	AC	50 ms 38,532 KB
testcase_11	AC	51 ms 38,328 KB
testcase_12	AC	173 ms 41,656 KB
testcase_13	AC	178 ms 41,520 KB
testcase_14	AC	228 ms 45,104 KB
testcase_15	AC	213 ms 44,588 KB
testcase_16	AC	145 ms 41,312 KB
testcase_17	AC	210 ms 44,580 KB
testcase_18	AC	152 ms 41,348 KB
testcase_19	AC	170 ms 41,616 KB
testcase_20	AC	213 ms 44,584 KB
testcase_21	AC	221 ms 44,956 KB
testcase_22	AC	230 ms 45,048 KB
testcase_23	AC	229 ms 45,136 KB
testcase_24	AC	232 ms 45,052 KB
testcase_25	AC	228 ms 45,056 KB
testcase_26	AC	228 ms 45,180 KB
testcase_27	AC	229 ms 45,052 KB
testcase_28	AC	229 ms 45,056 KB
testcase_29	AC	229 ms 45,060 KB
testcase_30	AC	228 ms 45,052 KB
testcase_31	AC	232 ms 45,060 KB
testcase_32	AC	231 ms 45,160 KB
testcase_33	AC	232 ms 45,140 KB
testcase_34	AC	237 ms 45,056 KB
testcase_35	AC	230 ms 45,180 KB
testcase_36	AC	225 ms 45,156 KB
testcase_37	AC	127 ms 41,312 KB
testcase_38	AC	128 ms 41,424 KB
testcase_39	AC	128 ms 41,304 KB
testcase_40	AC	125 ms 41,308 KB
testcase_41	AC	126 ms 41,244 KB
testcase_42	AC	87 ms 41,816 KB
testcase_43	AC	88 ms 41,832 KB
testcase_44	AC	90 ms 41,676 KB
testcase_45	AC	92 ms 41,848 KB
testcase_46	AC	117 ms 44,248 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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;
}

yukicoder

結果

テストケース

ソースコード