TopCoder SRM 656 Div1 Medium: PermutationCounts

問題

TopCoder Statistics - Problem Statement

解法

kmjp.hatenablog.jp

神様仏様kmjp様

コード

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Collections;

public class PermutationCounts {

	private final int MOD = 1000000007;
	BigInteger modInteger = new BigInteger(String.valueOf(MOD));

	public int countPermutations(int N, int[] pos) {
		ArrayList<Integer> posList = new ArrayList<>();
		for (int i = 0; i < pos.length; i++) {
			posList.add(pos[i]);
		}
		posList.add(0);
		posList.add(N);
		Collections.sort(posList);

		long[] fact = new long[N + 1];
		long[] factInv = new long[N + 1];

		fact[0] = factInv[0] = 1;
		for (int i = 1; i <= N; i++) {
			fact[i] = fact[i - 1] * i;
			fact[i] %= MOD;
			factInv[i] = factInv[i - 1] * (new BigInteger(String.valueOf(i))).modInverse(modInteger).longValue();
			factInv[i] %= MOD;
		}

		long[] dp = new long[posList.size()];
		dp[0] = 1;
		for (int i = 0; i < posList.size(); i++) {
			for (int j = 0; j < i; j++) {
				long pattern = dp[j] * factInv[posList.get(i) - posList.get(j)] % MOD;
				if ((i - j) % 2 == 0) {
					dp[i] += MOD - pattern;
				} else {
					dp[i] += pattern;
				}
			}
			dp[i] %= MOD;
		}
		return (int) (dp[posList.size() - 1] * fact[N] % MOD);
	}
}