http://codeforces.com/contest/932/problem/C
f(i,j) := P[i] (j=1)
f(i,j) := f(P[i], j-1) (otherwise)
と定義される関数fがある。
関数g(i)をf(i,j)=iとなる最小のjと定義する。
g(1), g(2), ..., g(N)の値がAかBのいずれかになるように順列Pを構築せよ。
不可能なら"-1"
解法
http://codeforces.com/contest/932/submission/35302250
よくある順列をiからP[i]へ辺を貼るグラフを考える。
すると、g(i)は頂点iから遷移してiに到達する最低回数を返す。
そのため、グラフを作成していくときに、連結成分がそれぞれ頂点数AかBとなるように作ればいい。
構築出来るかは、N=A*a+B*bのように表現できるかによる。
まずは、aを全探索して、N=A*a+B*bを満たすa,bを探そう。
あとは、A頂点毎にサイクルをa個作り、B頂点毎にサイクルをb個作って答える。
int N, A, B, ans[1010101]; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N >> A >> B; int aa = -1, bb = -1; rep(a, 0, N / A + 1) { int res = N - a * A; if (res % B == 0) { aa = a; bb = res / B; break; } } if (aa < 0) { printf("-1\n"); return; } int idx = 0; rep(a, 0, aa) { rep(i, 0, A - 1) ans[idx + i + 1] = idx + i; ans[idx] = idx + A - 1; idx += A; } rep(b, 0, bb) { rep(i, 0, B - 1) ans[idx + i + 1] = idx + i; ans[idx] = idx + B - 1; idx += B; } rep(i, 0, N) { if (i) printf(" "); printf("%d", ans[i] + 1); } printf("\n"); }