SRM477 DIV2 1000

这题还是看了官方的解题报告才明白怎么做的，动态规划加记忆化搜索。

$dp[n][k]$ 代表 $n$ 个人中有 $k$ 个人都拿错信件的状态数目，

• 当 $n=k=0$ 时：$dp[n][k]=1$
• $n=0$ 时：$dp[n][k]=0$
• $k=0$ 时：$dp[n][k]=n \times dp[n-1][k]$
• 否则：$dp[n][k]=(n-k) \times (dp[n-2][k-1]+dp[n-1][k])+(k-1) \times (dp[n-2][k-2]+dp[n-1][k-1])$

注意：当 $k=1$ 时，没有后半部分

const int MAX = 1100;
const LL mod = 1000000007;

LL dp[MAX][MAX];

LL dfs(int n, int k) {
  if (dp[n][k] != -1) return dp[n][k];
  if (n == 0 && k == 0)
    dp[n][k] = 1;
  else if (n == 0)
    dp[n][k] = 0;
  else if (k == 0)
    dp[n][k] = (n * dfs(n - 1, k)) % mod;
  else if (k == 1) {
    if (n > 1)
      dp[n][k] = ((n - k) * (dfs(n - 2, k - 1) + dfs(n - 1, k))) % mod;
    else
      dp[n][k] = 0;
  } else
    dp[n][k] = ((n - k) * (dfs(n - 2, k - 1) + dfs(n - 1, k)) +
                (k - 1) * (dfs(n - 2, k - 2) + dfs(n - 1, k - 1))) %
               mod;
  return (int)dp[n][k];
}

class CarelessSecretary {
 public:
  int howMany(int N, int K) {
    for (int i = 0; i <= N; i++)
      for (int j = 0; j <= K; j++) dp[i][j] = -1;
    return (int)dfs(N, K);
  }
};