AOJ 12/4

2014-12-04 | [Competitive programming]

2378 (SolveMe)

部屋の集合 S = {0, 1, …, N-1} とし，部屋 i からの右耳での行き先を f(i), 左耳での行き先を g(i) とする． f, g は S -> S の関数である．条件は f^Z・g・f^Y・g・f^X = id である．よって g は全単射で，X + Y + Z > 0 であれば f も全単射である． (X + Y + Z = 0 の場合は以下の議論は使えないが，f が全単射に限らないことを除いて結果が一致する) 全単射であるから，逆写像を自由にぶつけることができて便利である．

すると，適当な置き換えにより結局 S -> S の全単射 f, g で，f^2 = g^|X+Z-Y| なるものの数を数えればいいことになる． f^2 = g^|X+Z-Y| = h とおく．h を固定したときの f, g の数を数える気分で答えを求める．

S -> S の全単射は，一般に「サイクル」(f(0) = 1, f(1) = 2, f(2) = 0 のように，関数適用で循環するときの循環節) に分解できる．関数の繰り返し適用により，サイクルがどう分解するかを調べると，長さ l のサイクルは k 回適用のあとで，長さ l/gcd(l, k) のサイクル gcd(l, k) 個に分解することがわかる．

あとは，長さ l のサイクルがちょうど m 個与えられたとき，繰り返し適用の後でそれらに分解するような「サイクルたち」が何個あるか数える (DP)．この DP テーブルがあれば，h について (残りの要素, 次に割り当てるサイクル長) をキーに DP を行うことで解ける．

#include <cstdio>

#include <algorithm>

#include <vector>


using namespace std;
typedef long long i64;

const i64 MOD = 1000000007;

inline void ADD(i64& a, i64 b) { a = (a + b) % MOD; }
i64 gcd(i64 a, i64 b) {
	return b ? gcd(b, a % b) : a;
}

int N;
i64 X, Y, Z, K;
i64 C[2050][2050], frac[2050];

i64 dp[2][1010][1010];
i64 sol[1010][1010];

void solve(int t, i64 K)
{
	i64 ip[1010];

	for (int i = 1; i <= N; ++i) {
		vector<int> good;
		for (int j = 1; j <= N / i; ++j) {
			if (j == gcd(j * i, K)) good.push_back(j);
		}

		ip[0] = 1;
		for (int j = 1; j <= N / i; ++j) ip[j] = (ip[j - 1] * i) % MOD;

		dp[t][i][0] = 1;
		for (int j = 1; j <= N / i; ++j) {
			dp[t][i][j] = 0;
			for (int k : good) if (j >= k) {
				ADD(dp[t][i][j], frac[k - 1] * ip[k - 1] % MOD * C[j - 1][k - 1] % MOD * dp[t][i][j - k]);
			}
		}
	}
}

int main()
{
	scanf("%d%lld%lld%lld", &N, &X, &Y, &Z);
	K = X + Z - Y;
	if (K < 0) K = -K;

	for (int i = 0; i < 2050; ++i) C[0][i] = 0;
	C[0][0] = 1;

	for (int i = 1; i < 2050; ++i) {
		C[i][0] = 1;
		for (int j = 1; j < 2050; ++j) {
			C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
		}
	}
	frac[0] = 1;
	for (int i = 1; i < 2050; ++i) frac[i] = (frac[i - 1] * i) % MOD;

	solve(0, 2);
	solve(1, K);

	if (X == 0 && Y == 0 && Z == 0) {
		i64 ret = dp[0][1][N];
		for (int i = 0; i < N; ++i) ret = (ret * N) % MOD;
		printf("%lld\n", ret);
		return 0;
	}

	for (int i = 0; i <= N; ++i) sol[1][i] = 0;
	sol[1][N] = 1;

	i64 cyc_cnt[1010];

	for (int i = 1; i <= N; ++i) {
		for (int j = 0; j <= N; ++j) sol[i + 1][j] = 0;

		cyc_cnt[0] = 1;
		for (int j = 1; j <= N / i; ++j) {
			cyc_cnt[j] = cyc_cnt[j - 1] * C[i * j - 1][i - 1] % MOD * frac[i - 1] % MOD;
		}

		for (int j = 0; j <= N; ++j) {
			for (int k = 0; k <= j / i; ++k) {
				ADD(sol[i + 1][j - k * i], sol[i][j] * cyc_cnt[k] % MOD * C[j][k * i] % MOD * dp[0][i][k] % MOD * dp[1][i][k]);
			}
		}
	}

	printf("%lld\n", sol[N + 1][0]);

	return 0;
}

2234 (Usagitobi)

{(ax+cy mod m, bx+dy mod n) | x, y ∈ Z} の元の個数を求めるとよい．