#58456 (C++11) No.261 ぐるぐるぐるぐる！あみだくじ！

提出ソース

結果

問題	No.261 ぐるぐるぐるぐる！あみだくじ！
ユーザー	pekempey
提出日時	2015-11-12 22:13:45
言語	C++11 (gcc 11.4.0)
結果	AC
実行時間	3 ms / 5,000 ms
コード長	3,653 bytes
コンパイル時間	1,786 ms
コンパイル使用メモリ	189,556 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-09-13 14:32:18
合計ジャッジ時間	2,966 ms
ジャッジサーバーID （参考情報）	judge4 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	1 ms 5,376 KB
testcase_03	AC	1 ms 5,376 KB
testcase_04	AC	2 ms 5,376 KB
testcase_05	AC	2 ms 5,376 KB
testcase_06	AC	2 ms 5,376 KB
testcase_07	AC	2 ms 5,376 KB
testcase_08	AC	2 ms 5,376 KB
testcase_09	AC	2 ms 5,376 KB
testcase_10	AC	2 ms 5,376 KB
testcase_11	AC	2 ms 5,376 KB
testcase_12	AC	2 ms 5,376 KB
testcase_13	AC	2 ms 5,376 KB
testcase_14	AC	2 ms 5,376 KB
testcase_15	AC	2 ms 5,376 KB
testcase_16	AC	2 ms 5,376 KB
testcase_17	AC	2 ms 5,376 KB
testcase_18	AC	2 ms 5,376 KB
testcase_19	AC	2 ms 5,376 KB
testcase_20	AC	2 ms 5,376 KB
testcase_21	AC	3 ms 5,376 KB
testcase_22	AC	2 ms 5,376 KB
testcase_23	AC	2 ms 5,376 KB
testcase_24	AC	2 ms 5,376 KB
testcase_25	AC	2 ms 5,376 KB
testcase_26	AC	2 ms 5,376 KB
testcase_27	AC	2 ms 5,376 KB
testcase_28	AC	2 ms 5,376 KB
testcase_29	AC	2 ms 5,376 KB
testcase_30	AC	3 ms 5,376 KB
testcase_31	AC	2 ms 5,376 KB
testcase_32	AC	2 ms 5,376 KB
testcase_33	AC	2 ms 5,376 KB
testcase_34	AC	2 ms 5,376 KB
testcase_35	AC	2 ms 5,376 KB
testcase_36	AC	2 ms 5,376 KB
testcase_37	AC	2 ms 5,376 KB
testcase_38	AC	2 ms 5,376 KB
testcase_39	AC	2 ms 5,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
#define GET_MACRO(a, b, c, NAME, ...) NAME
#define rep(...) GET_MACRO(__VA_ARGS__, rep3, rep2)(__VA_ARGS__)
#define rep2(i, a) rep3 (i, 0, a)
#define rep3(i, a, b) for (int i = (a); i < (b); i++)
#define repr(...) GET_MACRO(__VA_ARGS__, repr3, repr2)(__VA_ARGS__)
#define repr2(i, a) repr3 (i, 0, a)
#define repr3(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define chmin(a, b) ((b) < a && (a = (b), true))
#define chmax(a, b) (a < (b) && (a = (b), true))
using namespace std;
typedef long long ll;

template<class T>
ostream &operator <<(ostream &os, const vector<T> &v) {
	rep (i, v.size()) {
		if (i) os << " ";
		os << v[i];
	}
	return os;
}

ll modulo(ll a, ll mod) {
	a %= mod; a += mod; a %= mod;
	return a;
}

pair<ll, ll> extgcd(ll a, ll b) {
	if (b == 0) return {1, 0};
	ll x, y;
	tie(x, y) = extgcd(b, a % b);
	return {y, x - a / b * y};
}

ll modinv(ll a, ll mod) {
	if (a == 0) return -1;
	if (__gcd(a, mod) != 1) return -1;
	return modulo(extgcd(a, mod).first, mod);
}

ll garner(vector<pair<ll, ll>> eq, ll mod) {
	eq.emplace_back(0, mod);
	int n = eq.size();
	vector<ll> coef(n, 1), sum(n, 0);
	rep (i, n - 1) {
		ll v = (eq[i].first - sum[i]) * modinv(coef[i], eq[i].second) % eq[i].second;
		if (v < 0) v += eq[i].second;
		rep (j, i + 1, n) {
			(sum[j] += coef[j] * v) %= eq[j].second;
			(coef[j] *= eq[i].second) %= eq[j].second;
		}
	}
	return sum.back();
}

map<ll, ll> primefactor(ll n) {
	map<ll, ll> res;
	for (ll i = 2; i * i <= n; i++) {
		while (n % i == 0) {
			res[i]++;
			n /= i;
		}
	}
	if (n != 1) res[n]++;
	return res;
}

vector<pair<ll, ll>> normalize(vector<pair<ll, ll>> eq) {
	vector<map<ll, ll>> pf(eq.size());
	rep (i, eq.size()) {
		pf[i] = primefactor(eq[i].second);
	}
	map<ll, pair<ll, ll>> pnum; // prime, value, index
	rep (i, pf.size()) {
		for (auto p : pf[i]) {
			if (pnum[p.first].first < p.second) {
				pnum[p.first].first = p.second;
				pnum[p.first].second = i;
			}
		}
	}
	for (auto p : pnum) {
		rep (i, eq.size()) if (i != p.second.second) {
			while (eq[i].second % p.first == 0) {
				eq[i].second /= p.first;
			}
			eq[i].first %= eq[i].second;
		}
	}
	return eq;
}

bool check(vector<pair<ll, ll>> eq) {
	rep (i, eq.size()) {
		rep (j, i + 1, eq.size()) {
			ll a1 = eq[i].first;
			ll a2 = eq[j].first;
			ll m1 = eq[i].second;
			ll m2 = eq[j].second;
			ll g = __gcd(m1, m2);
			ll l = m1 / g * m2;
			if ((a2 - a1) % g != 0) return false;
		}
	}
	return true;
}

int main() {
	int N, K;
	cin >> N >> K;
	vector<int> s(N);
	rep (i, N) s[i] = i;
	rep (i, K) {
		int X, Y;
		cin >> X >> Y;
		X--; Y--;
		swap(s[X], s[Y]);
	}

	vector<int> id(N, -1), index(N, -1), orbit(N);
	rep (i, N) if (id[i] == -1) {
		int curr = i;
		int j = 0;
		while (id[curr] == -1) {
			id[curr] = i;
			index[curr] = j++;
			orbit[i]++;
			curr = s[curr];
		}
	}

	int Q;
	cin >> Q;
	rep (i_, Q) {
		vector<int> A(N);
		rep (i, N) {
			cin >> A[i];
			A[i]--;
		}
		bool bad = false;
		vector<int> dist(N, -1);
		map<ll, ll> mp;
		rep (i, N) {
			if (id[i] != id[A[i]]) bad = true;
			else {
				int orb = orbit[id[i]];
				int d = modulo(index[A[i]] - index[i], orb);
				if (mp.count(orb)) {
					if (mp[orb] != d) bad = true;
				} else {
					mp[orb] = d;
				}
			}
		}
		if (bad) {
			cout << -1 << endl;
			continue;
		}

		vector<pair<ll, ll>> eq;
		for (auto kv : mp) {
			eq.emplace_back(kv.second, kv.first);
		}
		if (!check(eq)) {
			cout << -1 << endl;
			continue;
		}
		eq = normalize(eq);
		ll prod = 1;
		for (auto p : eq) prod *= p.second;
		const ll mod = 1e18;
		ll ans = garner(eq, mod);
		if (ans == 0) ans += prod;
		cout << ans << endl;
	}
	return 0;
}

yukicoder

結果

テストケース

ソースコード