結果

問題 No.3441 Sort Permutation 2
コンテスト
ユーザー startcpp
提出日時 2026-02-08 13:13:10
言語 C++14
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 373 ms / 2,000 ms
コード長 2,390 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,674 ms
コンパイル使用メモリ 98,472 KB
実行使用メモリ 18,040 KB
最終ジャッジ日時 2026-02-08 13:13:31
合計ジャッジ時間 20,466 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 41
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

// [2点swapと操作回数]
// i->P_iのグラフを考える。
// i,jを選ぶと、i->P_j, j->P_i に行き先が入れ替わる。それ以外は変わらない。(隣接swap以外なら{i, j}と{P_i, P_j}が排反なため。隣接swapは別途確認。)
// i,jを同じサイクルから選ぶとサイクルが分かれる。異なるサイクルから選ぶとサイクルが繋がる。
// 操作回数を最小化するには、i,jを同じサイクルから選び続ける必要がある。また、それで十分。
// ↑この辺の話は、適当な順列（何でもいいが、例えば P = (2 3 4 5 6 1)）で実際に試すと予想がつきやすい。定番の考察なので覚えてもよさそう。
//
// [余り/GCDなどを考える]
// 同じサイクルのなかの mod k が全て一致していれば、サイクルに含まれる頂点数 - 1 だけのダメージが確定する。
// 一致していなければ、好きな値を1つpopできる (自己ループにできる) ので、最後まで「mod kが2種類以上の状態」を保てて、ノーダメージにできる。
//
// [k=1,2,…,Nに対応する]
// サイクルの最小値が0になるよう値をシフトすると、「すべての頂点がkの倍数なら、ans_kに+C-1を寄与」とできる。(C=サイクルに含まれる頂点数)
// サイクルの値の最大公約数をgとするとき、gの「約数」であるようなkについて加算を行えばよい。
// a[g] += C-1 などとしておき、ans[k] = a[k] + a[2k] + a[3k] + ... とすればOK。調和級数でO(NlogN)に抑えられる。
// なお、愚直に加算をして時間のかかるケースがあるのかは…定かではない。

#include <iostream>
#include <atcoder/dsu>
#define rep(i, n) for(i = 0; i < n; i++)
using namespace std;
using namespace atcoder;

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

int n;
int p[200000];

int main() {
	int i;

	cin >> n;
	rep(i, n) { cin >> p[i]; p[i]--; }

	dsu uf(n);
	rep(i, n) uf.merge(i, p[i]);
	
	vector<int> a(n);
	for (auto gr: uf.groups()) {
		int minV = 1e+9;
		for (int v: gr) minV = min(minV, v);
		int g = 0;
		for (int v: gr) g = gcd(g, v - minV);
		a[g] += (int)gr.size() - 1;
	}

	for (i = 1; i < n; i++) {
		int ans = 0;
		for (int j = i; j < n; j += i) ans += a[j];
		cout << ans << endl;
	}
	return 0;
}
0