日記 (2018 年 3 月 13 日)

今日は AGC023 があったんですが、 そこの C 問題で階乗の逆元の求め方が分からず戸惑ってしまったので、 簡単にまとめておきます。 問題はこちらです。

面倒なので詳細は省きますが、 どんな順列に対しても、 そのスコア s は必ず (N+1)/2sN1 の範囲になります。 また、 この範囲の s に対し、 スコア s 以下の順列の個数は (s1)!s!/(2sN)! で求まります。 ということで、 階乗の積や商を求めることができればこの問題は解けるのですが、 普通に計算したら 8 バイト整数の範囲すら超えるので、 109+7 を法とする積や商の求め方を知っている必要があります。 以下、 P=109+7 とし、 合同式は P を法とします。

まず、 2 つの数 ab の積を mod P のもとで計算するのは簡単で、 普通に積を計算した後に P での剰余をとるだけです。 では、 ab の商はどうするかというと、 b の逆元を計算して、 これと a との積を計算します。 P は素数なのでフェルマーの小定理を使うと、 b の逆元は bP2 で求まることが分かるので、 積の計算に帰着できます。 愚直に P2 回積を計算するのは効率が悪いので、 以下のように二分累乗法を用いましょう。

public static final int MOD = 1000000007;
public long pow(long a, long b) {
if (b == 0) {
return 1;
} else if (b % 2 == 0) {
long d = pow(a, b / 2);
return (d * d) % MOD;
} else {
long d = pow(a, b - 1);
return (a * d) % MOD;
}
}

さて、 すでに述べたように、 この問題では階乗の積や商の計算を何度も行うので、 あらかじめ階乗とその逆元の値を計算しておきます。 階乗の逆元は、 毎回階乗の P2 乗を計算するよりも、 n!1=(n+1)!1·(n+1) という関係を使うことで、 より効率的に計算できます。

public long[][] calcFact(int n) {
long[] fact = new long[n];
long[] invfact = new long[n];
fact[0] = 1;
for (int i = 1 ; i < n ; i ++) {
fact[i] = (fact[i - 1] * i) % MOD;
}
invfact[n - 1] = pow(fact[n - 1], MOD - 2);
for (int i = n - 2 ; i >= 0 ; i --) {
invfact[i] = invfact[i + 1] * (i + 1) % MOD;
}
return new long[][]{fact, invfact};
}

というわけで、 あとはこれらのメソッドを使って解答を計算するだけです。

public void run() {
BetterScanner scanner = new BetterScanner(System.in);
int n = scanner.nextInt();
long[][] fact = calcFact(n);
long res = 0;
long prev = 0;
for (int s = (n + 1) / 2 ; s <= n - 1 ; s ++) {
long val = fact[0][s - 1] * fact[0][s] % MOD * fact[1][2 * s - n] % MOD;
res = (s * (val - prev + MOD) % MOD + res) % MOD;
prev = val;
}
System.out.println(res);
}