結果

問題 No.1482 Swap Many Permutations
ユーザー nok0
提出日時 2021-03-02 22:46:03
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,744 bytes
コンパイル時間 4,177 ms
コンパイル使用メモリ 258,632 KB
最終ジャッジ日時 2025-01-19 09:36:17
ジャッジサーバーID
（参考情報） 		judge5 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 2
other WA * 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_;

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[i * i % m] = 1;
	};

	convolution_init();
	quadratic_residue_init();

	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) 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++) {
		int b, c;
		cin >> b >> c;
		sum_pality += decode_inversion(b, c);
		cout << solver(i).val() << endl;
	}

	return 0;
}
0