Particle

競技プログラミングについての雑記

AOJ 2378: SolveMe

問題

A^{X}BA^{Y}BA^{Z}=I
となるようなA, Bの組の個数を1,000,000,007で割ったものを求める. (A, Bの条件については問題文参照)

解法

まず
A^{X}BA^{Y}BA^{Z}=I
B=B'^{-1}A^{-Y}を代入し整理すると、B'^{2}=A^{X-Y+Z}となる.
\sum_{u}^{} \frac{\left(\sum_{v}^{} D(v)\right)\left(\sum_{w}^{} D(w)\right)}{D(u)}
を求めれば良い.
ただし、u, v, w は N次元ベクトルで、 (uの表す置換) = (vの表す置換)^2 = (wの表す置換)^{X-Y+Z}で、置換の大きさは同じであるとする. 置換の大きさは、
 K = sum_{k=1}^{N} ku_{k}
と表される. これは、 大きさkの巡回置換がu_{k}個含まれていることを示している.
D(u) = K! \prod_{i=1}^{N} \frac{1}{\left(iu_{i}\right)!}\prod_{j=1}^{u_{i}}\binom{ij-1}{i-1}\left(i-1\right)!
である.
標準基底のスカラー倍について計算してから、DPで計算すればよい.
実際に計算する場合は、D(u)K!で割ったものを計算するほうが簡単である.
コーナーケースがあるので注意する.

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
#define N 1024
ll inv[N], fact[N], ifact[N], D[N][N], iD[N][N], dp[N][N], dp2[2][N][N];
ll mod = 1000000007;
ll n, x, y, z, t[2];
void update(ll a, ll t, ll d[][N]){
	d[a][0] = 1;
	int v = __gcd(a, t);
	int b = a/v;
	for(int i = n/b; i >= 1; i--)
		for(int j = 1; j <= i/v; j++)
			(d[b][i]+=d[b][i-j*v]*D[a][j])%=mod;
}
int main(){
	scanf("%ld%ld%ld%ld",&n,&x,&y,&z);
	t[0] = abs(x-y+z);
	t[1] = 2;
	inv[1] = 1;
	for(int i = 2; i <= n; i++) inv[i] = inv[mod%i]*(mod-mod/i)%mod;
	fact[0] = ifact[0] = 1;
	for(int i = 1; i <= n; i++){
		fact[i] = fact[i-1]*i%mod;
		ifact[i] = ifact[i-1]*inv[i]%mod;
	}
	for(int i = 1; i <= n; i++){
		D[i][0] = iD[i][0] = 1;
		for(int j = 1; j <= n/i; j++){
			D[i][j] = D[i][j-1]*inv[i*j]%mod;
			iD[i][j] = iD[i][j-1]*i*j%mod;
		}
	}
	if(!x&&!y&&!z){
		for(int i = 1; i <= 2; i++) update(i, t[0], dp2[0]);
		ll res = dp2[0][1][n]*fact[n]%mod;
		for(int i = 0; i < n; i++) (res*=n)%=mod;
		printf("%ld\n", res);
		return 0;
	}
	for(int i = 1; i <= n; i++)
		for(int j = 0; j < 2; j++)
			update(i, t[j], dp2[j]);
	dp[0][0] = 1;
	for(int i = 1; i <= n; i++)
		for(int j = 0; j <= n; j++)
			for(int k = 0; k <= j/i; k++)
				(dp[i][j]+=dp[i-1][j-i*k]*dp2[0][i][k]%mod*dp2[1][i][k]%mod*iD[i][k])%=mod;
	printf("%ld\n",dp[n][n]*fact[n]%mod);
	return 0;
}