結果

問題 No.590 Replacement
コンテスト
ユーザー e869120
提出日時 2018-06-09 20:14:57
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,139 bytes
コンパイル時間 1,468 ms
コンパイル使用メモリ 109,568 KB
実行使用メモリ 24,708 KB
最終ジャッジ日時 2024-06-30 12:59:28
合計ジャッジ時間 8,182 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 7 WA * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <tuple>
#include <map>
#include <algorithm>
using namespace std;

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;

int modpow(int a, int b, int mod) {
	long long p = 1, q = a;
	for (int i = 0; i < 30; i++) {
		if ((b / (1 << i)) % 2 == 1) { p *= q; p %= mod; }
		q *= q; q %= mod;
	}
	return p;
}
int Div(int a, int b, int mod) {
	return (1LL * a*modpow(b, mod - 2, mod)) % mod;
}

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 gcd(int a, int b) {
	if (b == 0) return a;
	return gcd(b, a%b);
}

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 T = 1LL * cnt1[i] * (K / F1) + 1LL * cnt2[i] * (K / F2); if (T >= K) T -= K;
		long long U = (cnt1[i] - cnt2[i] + K) % KK;
		long long TT = Div(((K / F1) + (K / F2)) % K, T, K);

		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 (GG <= 0) GG += MM[G[i]];
			ans += GG * (GG - 1) / 2; ans %= 1000000007;
		}
	}
	cout << ans << endl;
	return 0;
}
0