#746507 (C++23) No.1881 Everything is the same...

• 問題: No.1881 Everything is the same...
• ユーザー: cologne
• 提出日時: 2022-03-17 23:36:41
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 2,634 bytes
• コンパイル時間: 2,082 ms
• コンパイル使用メモリ: 218,004 KB
• 実行使用メモリ: 6,400 KB
• 最終ジャッジ日時: 2026-04-18 22:44:09
• 合計ジャッジ時間: 5,285 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge2_1

ファイルパターン	結果
other	AC * 45 WA * 7

ソースコード

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

using namespace std;

vector<vector<int>> gen(vector<int> V)
{
	int sz = 1;
	for (int x : V)
		sz *= x;
	vector<vector<int>> R;
	for (int i = 0; i < sz; ++i)
	{
		int n = i;
		vector<int> U;
		for (int a : V)
		{
			U.push_back(n % a);
			n /= a;
		}
		R.push_back(U);
	}
	return R;
}

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

	for (vector<int> x : V)
	{
		vector<int> d(x.size());
		for (int i = 0; i < (int)d.size(); ++i)
			d[i] = x[i] - (i == 0 ? 0 : x[i - 1]) + 1;
		vector<vector<int>> tot;
		for (auto mx : gen(d))
		{
			vector<int> n(x.size());
			for (int i = 0; i < (int)n.size(); ++i)
				n[i] = x[i] - mx[i];
			if (n.front() == 0)
				n.erase(n.begin());
			tot.push_back(n);
		}
		tr.push_back(tot);
	}

	vector<int> mex;

	vector<int> d(V.size());
	for (int i = 0; i < (int)d.size(); ++i)
		d[i] = tr[i].size();
	auto g = gen(d);
	g.erase(g.begin());

	for (auto nx : g)
	{
		vector<vector<int>> U;
		for (int i = 0; i < (int)d.size(); ++i)
			if (!tr[i][nx[i]].empty())
				U.push_back(tr[i][nx[i]]);
		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] = {};
		C[p].push_back(k);
	};

	// 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 &v : cyc)
		sort(v.begin(), v.end());
	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";
}