[COCI2019-2020#5] Zapina
题意
有 \(n\) 个不同的人和 \(n\) 道不同的题。
第 \(i\) 个人开心当且仅当他被分配到 \(i\) 道题。
求让至少一个人开心的分配方案数。、
思路1
定义 \(dp_{i,j}\) 表示前 \(i\) 个人发 \(j\) 道题，没人开心的方案数。
答案等于 \(n^n-dp_{n,n}\)。
\[dp_{i,j}=\sum dp_{i-1,k}\times C_{n-k}^{j-k} (j-k\ne i) \]即枚举现在的题数，上次的题数，相减不等于 \(i\) 即可转移，乘上组合数。
代码1
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 350 + 5;
const int mod = 1e9 + 7;
int c[N][N], n;
int dp[N][N];
int qpow(int a, int b) {
int res = 1;
for (; b; b >>= 1, a = a * a % mod)
if (b & 1) res = res * a % mod;
return res;
}
void solve() {
cin >> n;
for (int i = 0; i <= n; i ++) c[i][0] = 1;
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= i; j ++)
c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
dp[0][0] = 1;
for (int i = 1; i <= n; i ++) {
for (int j = 0; j <= n; j ++) {
for (int k = 0; k <= j; k ++) {
if (j - k != i) dp[i][j] += dp[i - 1][k] * c[n - k][j - k];
dp[i][j] %= mod;
}
}
}
cout << (qpow(n, n) - dp[n][n] + mod) % mod << "\n";
}
signed main() {
int Case = 1;
// cin >> Case;
while (Case --)
solve();
return 0;
}
思路2
定义 \(dp_{i,j}\) 表示前 \(i\) 个人发 \(j\) 道题，至少有一个人开心。
- 让 \(i\) 开心。\(dp_{i,j}=C_{j}^{i}\times(i-1)^{j-i}\)。选 \(i\) 道给 \(i\)，剩下的随便放，每道题有 \((i-1)\) 种情况，有 \((j-i)\) 道题， 所以是 \((i-1)^{j-i}\)。
- 让 \(i\) 不开心。\(dp_{i,j}=\sum dp_{i-1,j-k}\times C_{j}^{k}(k \ne i)\)（其实和思路1等价）。
代码2
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 350 + 5;
const int mod = 1e9 + 7;
int c[N][N], n;
int dp[N][N];
int qpow(int a, int b) {
int res = 1;
for (; b; b >>= 1, a = a * a % mod)
if (b & 1) res = res * a % mod;
return res;
}
void solve() {
cin >> n;
for (int i = 0; i <= n; i ++) c[i][0] = 1;
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= i; j ++)
c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
for (int i = 1; i <= n; i ++) {
for (int j = 0; j <= n; j ++) {
if (j >= i) dp[i][j] += c[j][i] * qpow(i - 1, j - i) % mod;
for (int k = 0; k <= j; k ++) {
if (i != k) dp[i][j] += dp[i - 1][j - k] * c[j][k] % mod;
}
dp[i][j] %= mod;
}
}
cout << dp[n][n] << "\n";
}
signed main() {
int Case = 1;
// cin >> Case;
while (Case --)
solve();
return 0;
}