結果

問題 No.1482 Swap Many Permutations
ユーザー nok0nok0
提出日時 2021-03-02 23:19:39
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,873 bytes
コンパイル時間 4,068 ms
コンパイル使用メモリ 270,828 KB
実行使用メモリ 44,508 KB
最終ジャッジ日時 2024-10-04 16:59:53
合計ジャッジ時間 12,657 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
testcase_38 WA -
testcase_39 WA -
testcase_40 WA -
testcase_41 WA -
testcase_42 WA -
testcase_43 WA -
testcase_44 WA -
testcase_45 WA -
testcase_46 WA -
権限があれば一括ダウンロードができます

ソースコード

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_;

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

	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; i++) {
			if(i % 2)
				odd[i] = finv[i] * finv[i];
			else
				even[i] = finv[i] * 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;
	};

	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 fac[m];
		}
		if(k % 2) {
			return even_odd[k] * fac[k] * fac[k] * fac[k] / 4;
		} else {
			if(sum_pality % 2)
				return odd_odd[k] * fac[k] * fac[k] * fac[k] / 4;
			else
				return even_even[k] * fac[k] * fac[k] * fac[k] / 4;
		}
	};

	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