日記 (2018 年 3 月 13 日)
今日は AGC023 があったんですが、 そこの C 問題で階乗の逆元の求め方が分からず戸惑ってしまったので、 簡単にまとめておきます。 問題はこちらです。
面倒なので詳細は省きますが、 どんな順列に対しても、 そのスコア
まず、 2 つの数
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;
}
}
さて、 すでに述べたように、 この問題では階乗の積や商の計算を何度も行うので、 あらかじめ階乗とその逆元の値を計算しておきます。
階乗の逆元は、 毎回階乗の
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);
}