World Codesprint 10: Permutation Happiness
https://www.hackerrank.com/contests/world-codesprint-10/challenges/permutation-happiness
解法
DP。1~n の順列に n+1 を挿入するイメージで更新していく。山の頂上(極大点)の個数を状態として持つと良い。dp[i: 順列のサイズ][j: 頂上の個数]
とする。
(1) 頂上の隣に挿入した場合は、頂上の個数は変わらない。2j 通り。
(2) それ以外の場所に挿入すると、頂上の個数が一つ増える。i+1-2j 通り。
#include <iostream> #include <cstdio> #include <vector> const int mod = 1e9 + 7; struct modint { int n; modint(int n = 0) : n(n) {} }; modint operator+(modint a, modint b) { return modint((a.n += b.n) >= mod ? a.n - mod : a.n); } modint operator-(modint a, modint b) { return modint((a.n -= b.n) < 0 ? a.n + mod : a.n); } modint operator*(modint a, modint b) { return modint(1LL * a.n * b.n % mod); } modint &operator+=(modint &a, modint b) { return a = a + b; } modint &operator-=(modint &a, modint b) { return a = a - b; } modint &operator*=(modint &a, modint b) { return a = a * b; } int main() { int q; std::cin >> q; const int N = 3000; std::vector<std::vector<modint>> dp(N + 1, std::vector<modint>(N + 1)); dp[1][1] = 1; for (int i = 1; i < N; i++) { for (int j = 0; j <= i; j++) { dp[i + 1][j] += dp[i][j] * (2 * j); dp[i + 1][j + 1] += dp[i][j] * (i + 1 - 2 * j); } } while (q--) { int n, k; std::cin >> n >> k; modint ans = 0; for (int i = 0; i <= N; i++) { if (n - i >= k) { ans += dp[n][i]; } } std::cout << ans.n << std::endl; } }