結果

問題 No.590 Replacement
ユーザー e869120e869120
提出日時 2018-06-09 21:33:15
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 274 ms / 2,000 ms
コード長 2,787 bytes
コンパイル時間 1,480 ms
コンパイル使用メモリ 109,252 KB
実行使用メモリ 24,708 KB
最終ジャッジ日時 2024-07-05 20:41:05
合計ジャッジ時間 8,972 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 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 13 ms
5,376 KB
testcase_08 AC 8 ms
5,376 KB
testcase_09 AC 14 ms
5,376 KB
testcase_10 AC 9 ms
5,376 KB
testcase_11 AC 4 ms
5,376 KB
testcase_12 AC 14 ms
5,376 KB
testcase_13 AC 65 ms
5,376 KB
testcase_14 AC 115 ms
5,752 KB
testcase_15 AC 7 ms
5,376 KB
testcase_16 AC 28 ms
5,376 KB
testcase_17 AC 48 ms
5,376 KB
testcase_18 AC 155 ms
7,356 KB
testcase_19 AC 201 ms
7,324 KB
testcase_20 AC 37 ms
5,376 KB
testcase_21 AC 263 ms
8,120 KB
testcase_22 AC 185 ms
8,008 KB
testcase_23 AC 222 ms
8,164 KB
testcase_24 AC 212 ms
8,052 KB
testcase_25 AC 212 ms
8,324 KB
testcase_26 AC 230 ms
8,060 KB
testcase_27 AC 216 ms
8,432 KB
testcase_28 AC 242 ms
8,056 KB
testcase_29 AC 234 ms
8,004 KB
testcase_30 AC 274 ms
8,040 KB
testcase_31 AC 238 ms
8,032 KB
testcase_32 AC 238 ms
8,408 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 107 ms
8,528 KB
testcase_37 AC 107 ms
8,520 KB
testcase_38 AC 104 ms
8,524 KB
testcase_39 AC 104 ms
8,524 KB
testcase_40 AC 249 ms
17,792 KB
testcase_41 AC 244 ms
17,792 KB
testcase_42 AC 106 ms
8,288 KB
testcase_43 AC 106 ms
8,272 KB
testcase_44 AC 178 ms
24,708 KB
testcase_45 AC 108 ms
8,524 KB
testcase_46 AC 106 ms
8,520 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <tuple>
#include <map>
#include <algorithm>
using namespace std;
#pragma warning (disable: 4996)

int N, A[100009], B[100009], col1[100009], cnt1[100009], S1[100009], col2[100009], cnt2[100009], S2[100009], cnts1, cnts2;
vector<tuple<int, int, int>>G;
map<tuple<int, int, int>, vector<long long>>M;
map<tuple<int, int, int>, long long>MM;

long long extgcd(long long a, long long b, long long &x, long long &y) {
	long long d = a;
	if (b != 0) {
		d = extgcd(b, a%b, y, x);
		y -= (a / b) * x;
	}
	else {
		x = 1; y = 0;
	}
	return d;
}

long long gcd(long long a, long long b) {
	if (b == 0) return a;
	return gcd(b, a%b);
}

long long solve(long long s1, long long s2, long long v, long long &x, long long &y) {
	if (gcd(s1, s2) >= 2) {
		return solve(s1 / gcd(s1, s2), s2 / gcd(s1, s2), v / gcd(s1, s2), x, y);
	}
	else if (v != 1) {
		solve(s1, s2, 1, x, y);
		x *= v; y *= v;
		x %= (s1 * s2 / gcd(s1, s2));
		y %= (s1 * s2 / gcd(s1, s2));
		return 0;	
	}
	else {
		return extgcd(s1, s2, x, y);
	}
}

long long division(long long p, long long s1, long long q, long long s2) {
	long long x, y;
	solve(s1, s2, q - p, x, y);
	long long G = (s1 * s2 / gcd(s1, s2));
	return (x * s1 + p + G * 100000000LL) % G;
}

void dfs1(int pos, int v) {
	col1[pos] = cnts1; cnt1[pos] = v; S1[cnts1]++;
	if (col1[A[pos]] == 0) { dfs1(A[pos], v + 1); }
}
void dfs2(int pos, int v) {
	col2[pos] = cnts2; cnt2[pos] = v; S2[cnts2]++;
	if (col2[B[pos]] == 0) { dfs2(B[pos], v + 1); }
}

int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) cin >> A[i];
	for (int i = 1; i <= N; i++) cin >> B[i];
	for (int i = 1; i <= N; i++) { if (col1[i] == 0) { cnts1++; dfs1(i, 0); } }
	for (int i = 1; i <= N; i++) { if (col2[i] == 0) { cnts2++; dfs2(i, 0); } }
	for (int i = 1; i <= N; i++) {
		long long F1 = S1[col1[i]], F2 = S2[col2[i]], K = F1*F2 / gcd(F1, F2), KK = gcd(F1, F2);
		long long U = (cnt2[i] - cnt1[i] + K) % KK;

		if (K == 1720) {
			K += 0;
		}

		long long TT = division(cnt1[i], F1, cnt2[i] - U, F2);

		//cout << "A = " << cnt1[i] << ", B = " << cnt2[i] << ", K = " << K << ", Z = " << TT << endl;

		G.push_back(make_tuple(col1[i], col2[i], U));
		M[make_tuple(col1[i], col2[i], U)].push_back(TT);
		MM[make_tuple(col1[i], col2[i], U)] = K;
	}
	sort(G.begin(), G.end()); G.erase(unique(G.begin(), G.end()), G.end());

	long long ans = 0;

	for (int i = 0; i < G.size(); i++) {
		vector<long long> Z = M[G[i]];
		sort(Z.begin(), Z.end()); long long B = Z[0];
		for (int j = 0; j < Z.size(); j++) Z[j] -= B;

		for (int j = 0; j < Z.size(); j++) {
			long long GG = Z[(j + 1) % Z.size()] - Z[j]; if (j == Z.size() - 1) GG += MM[G[i]];
			GG %= 1000000007;
			ans += GG * (GG - 1) / 2; ans %= 1000000007;
		}
	}
	cout << ans << endl;
	return 0;
}
0