結果

問題 No.1881 Everything is the same...
コンテスト
ユーザー cologne
提出日時 2022-03-18 11:35:23
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,740 bytes
コンパイル時間 1,005 ms
コンパイル使用メモリ 108,020 KB
最終ジャッジ日時 2024-11-15 02:11:15
合計ジャッジ時間 1,489 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp: In function 'int solve(const std::vector<std::vector<int> >&)':
main.cpp:70:17: error: 'sort' was not declared in this scope; did you mean 'short'?
   70 |                 sort(U.begin(), U.end());
      |                 ^~~~
      |                 short
main.cpp:74:9: error: 'sort' was not declared in this scope; did you mean 'short'?
   74 |         sort(mex.begin(), mex.end());
      |         ^~~~
      |         short
main.cpp:75:19: error: 'unique' was not declared in this scope
   75 |         mex.erase(unique(mex.begin(), mex.end()), mex.end());
      |                   ^~~~~~
main.cpp: In function 'int nimber(int)':
main.cpp:152:9: error: 'sort' was not declared in this scope; did you mean 'short'?
  152 |         sort(cyc.begin(), cyc.end());
      |         ^~~~
      |         short

ソースコード

diff # 

#include <cassert>
#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)
{
	int ox = x;
	static 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;
				}
				if (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;
			}
			if (k)
				add(p, k);
		}
	}
	if (x != 1)
		add_n(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[ox] = solve(cyc);
}

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