結果

問題 No.1881 Everything is the same...
コンテスト
ユーザー cologne
提出日時 2022-03-17 19:13:30
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 2,358 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,017 ms
コンパイル使用メモリ 213,908 KB
実行使用メモリ 1,308,416 KB
最終ジャッジ日時 2026-04-18 22:44:09
合計ジャッジ時間 5,865 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 WA * 2 RE * 6 MLE * 2 -- * 38
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <map>
#include <numeric>
#include <vector>

using namespace std;

int solve(const vector<vector<int>> &V)
{
	static map<vector<vector<int>>, int> M;
	if (M.count(V))
		return M[V];
	if (V.size() == 0)
		return 0;

	vector<vector<vector<int>>> transition(V.size());

	vector<int> mex;
	for (int i = 0; i < (int)V.size(); i++)
		for (int j = 0; j < (int)V[i].size(); ++j)
			if (V[i][j])
			{
				for (int k = -1; k < j; ++k)
				{
					auto U = V[i];
					U[j]--;
					if(k != -1)U[k]++;
					if (U.back() == 0)
						U.pop_back();
					sort(U.begin(), U.end());
					transition[i].push_back(U);
				}
			}
	int tot = 1;
	for(auto x: transition) tot *= x.size();
	for(int y = 1; y<tot; ++y)
	{
		vector<vector<int>> U;
		int ny = y;
		for(auto x: transition)
		{
			vector<int> tar = x[ny % x.size()];
			if(!tar.empty()) U.push_back(tar);
			ny /= x.size();
		}
		sort(U.begin(), U.end());
		mex.push_back(solve(U));
	}

	sort(mex.begin(), mex.end());
	mex.erase(unique(mex.begin(), mex.end()), mex.end());
	for (int i = 0; i < (int)mex.size(); ++i)
		if (mex[i] != i)
			return M[V] = i;

	return M[V] = mex.size();
}

int nimber(int x)
{
	map<int, int> M;
	if (M.count(x))
		return M[x];

	map<int, vector<int>> C;

	// add C_(p^k)
	auto add = [&](int p, int k)
	{
		if (!C.count(p))
			C[p] = {};
		if ((int)C[p].size() < k)
			C[p].resize(k);
		C[p][k - 1]++;
	};

	// adds C_n
	auto add_n = [&](int n)
	{
		for (int p = 2; p * p <= n; p++)
			if (n % p == 0)
			{
				int k = 0;
				while (n % p == 0)
				{
					n /= p;
					++k;
				}
				add(p, k);
			}
		if (n != 1)
			add(n, 1);
	};

	// Divide into cyclic group

	// Z^{2^k} divides into C^{2} * C^{2^{k-2}}
	int k = 0;
	while (x %2 == 0)
		x /= 2, ++k;

	if (k > 1)
		add(2, 1);
	if (k > 2)
		add(2, k - 2);
	for (int p = 3; p * p <= x; p += 2)
	{
		if (x % p == 0)
		{
			x /= p;
			add_n(p - 1);
			int k = 0;
			while (x % p != 0)
			{
				x /= p;
				++k;
			}
			add(p, k);
		}
	}
	if (x != 1)
		add(x, 1);

	vector<vector<int>> cyc;
	for (auto [a, b] : C)
		cyc.push_back(b);
	sort(cyc.begin(), cyc.end());
	/*for(auto x: cyc)
	{
		for(auto y: x) cout << y << " ";
		cout << endl;
	}*/
	return M[x] = solve(cyc);
}

int main()
{
	int N;
	cin >> N;
	int a = 0;
	while (N--)
	{
		int k; cin >> k;
		a ^= nimber(k);
	}
	if(a) cout << "Y\n";
	else cout << "X\n";
}
0