#1163052 (D) No.3529 2p Teleportations

• 問題: No.3529 2p Teleportations
• ユーザー: ジュ・ビオレ・グレイス
• 提出日時: 2026-05-05 00:20:44
• 言語: D (dmd 2.112.0)
• 結果: TLE
• 実行時間: -
• コード長: 2,451 bytes
• コンパイル時間: 590 ms
• コンパイル使用メモリ: 87,764 KB
• 実行使用メモリ: 16,192 KB
• 最終ジャッジ日時: 2026-05-05 00:21:10
• 合計ジャッジ時間: 5,982 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge1_1

ファイルパターン	結果
sample	AC * 1
other	TLE * 1 -- * 48

ソースコード

import std.stdio, std.algorithm, std.array, std.range, std.conv, std.typecons;

alias Perm = ulong[];

Perm composite(Perm a, Perm b) {
	assert(a.length == b.length);
	Perm c;
	foreach (i; 0 .. a.length) {
		c ~= a[b[i]];
	}
	return c;
}

Perm power(Perm a, ulong n) {
	return n == 0 ? iota(a.length).array : composite(power(a, n-1), a);
}

Perm inv(Perm a) {
	Perm b; b.length = a.length;
	foreach (i; 0 .. a.length) b[a[i]] = i;
	return b;
}

Perm[] cycle_decompose(Perm a) {
	Perm[] cycles;
	
	bool[] appeared; appeared.length = a.length;
	foreach (i; 0 .. a.length) {
		if (appeared[i]) continue;
		auto j = i;
		Perm cycle;
		do {
			appeared[j] = true;
			cycle ~= j;
			j = a[j];
		} while (j != i);
		cycles ~= cycle;
	}
	
	return cycles;
}

Perm to_perm(ulong[] c, ulong N) {
	auto result = iota(N).array;
	foreach (i; 0 .. c.length) {
		result[c[i]] = c[(i+1)%c.length];
	}
	return result;
}

ulong inv(ulong n, ulong l) {
	foreach (i; 1 .. l) if (n*i % l == 1) return i;
	assert(0, n.to!string ~ " " ~ l.to!string);
}

ulong[] solve(Perm a, ulong p) {
	auto N = a.length;
	auto cycles = cycle_decompose(a);
	
	Perm[][] c_by_len; c_by_len.length = N + 1;
	foreach (i; 0 .. a.length+1) c_by_len[i] = [];
	foreach (cycle; cycles) { c_by_len[cycle.length] ~= cycle; }
	
	Perm result; result = iota(a.length).array;
	
	foreach (l; 2 .. N+1) {
		if (l % 2 == 1) {
			auto k = inv(2*p, l);
			foreach (c; c_by_len[l]) result = result.composite(c.to_perm(N).inv().power(k));
		}
		else {
    		while (c_by_len[l].length >= 2) {
        		auto c1 = c_by_len[l][0];
        		auto c2 = c_by_len[l][1];
        		c_by_len[l] = c_by_len[l][2 .. $];
        		
        		Perm c;
        		foreach (i; 0 .. l) { c ~= c1[i], c ~= c2[i]; }
        		auto k = inv(p, l);
        		result = result.composite(c.to_perm(N).inv().power(k));
    		}
    		if (c_by_len[l].length == 1) {
    		    auto c = c_by_len[l][0];
    			if (l > 2) {
    		    	auto k = inv(2*p, l-1);
    		    	result = result.composite(c[0 .. l-1].to_perm(N).inv().power(k));
    		    }
    		    result[c[l-1]] = c[0];
	    	}
		}
	}
	
	return result;
}


void main() {
	auto T = readln[0 .. $-1].to!ulong;
	Perm[] perms; ulong[] primes;
	
	foreach (_; 0 .. T) {
		primes ~= readln.split.to!(ulong[])[1];
		perms ~= readln.split.to!(ulong[]).map!(x => x-1).array;
	}
	
	foreach (t; 0 .. T) {
		auto B = solve(perms[t], primes[t]);
		foreach (n; B) write(n+1, " ");
		writeln; 
	}
}