September Cook-Off 2012 PPERM : Prime Permutations

問題概要

長さNの置換pがprime permutationであるとは各iについて最初のi個の数字の中でp[i]がX番目(X=1or素数)に小さいようなものを言う。各iについて長さiのprime permutationがいくつあるか求める問題。

解法

p(i)をi以下の素数の個数とする。今、ans[i+1]を考える。i+1の入る場所の候補は1+p(i+1)通りある。[1..i]の入る場所はi+1を無視してよいのでans[i]通りある。したがってans[i+1] = (1 + p(i+1)) * ans[i]となる。
本番中は実験して通した。

acceptされたコード

int N;

void init() {
	scanf("%d", &N);
}

const int MAX_N = int(5e6);
int ans[MAX_N + 1];

int solve() {
	return ans[N];
}

const int MAX_SEIVE = ::MAX_N;
bool isPrime[MAX_SEIVE + 1];

void buildPrimeTable() {
	memset(isPrime, true, sizeof(isPrime));
	isPrime[0] = isPrime[1] = false;
	for (int i = 2; i*i <= MAX_SEIVE; i++) if (isPrime[i]) {
		for (int j = i<<1; j <= MAX_SEIVE; j += i) {
			isPrime[j] = false;
		}
	}
}


void presolve() {
	ans[1] = 1;
	int cnt = 1;
	for (int i = 2; i <= MAX_N; ++i) {
		if (isPrime[i]) {
			++cnt;
		}
		ans[i] = ans[i-1] * int64(cnt) % MOD;
	}
}

int main() {
	buildPrimeTable();
	presolve();
	int T; scanf("%d", &T);
	for (int _ = 0; _ < T; ++_) {
		init();
		printf("%d\n", solve());
	}
	return 0;
}