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; }