题解：P4007. [COCI2019-2020#5] Zapina

题目

有 个不同的人和 道不同的题。
第 个人开心当且仅当他被分配到 道题。
求让至少一个人开心的分配方案数。

题解

组合计数，正难则反。

• 考虑总分配方案数，从物品角度出发，每个物品可以选择任意一个人，共 种；
• 考虑前 个人分配 道题目仍然无人开心的方案数，记为 ；

答案就是 。

主要问题在于那个看上去很像动态规划的东西，，不妨用动态规划的思路试一下。

• 很常规的表示为前 个人分 个物品的方案数；
• 前 个无人开心，可以理解为前 个无人开心且 不开心；
• 假如我们已经有了正确的 ，现在需要求出 ；
• 在总共 个物品下，所有的 不开心的方案与其对应的 构成 ；
• 题目是两两不同的，所以选择 道题的同时还要考虑是哪些题，方案数为组合数；

所以递推式就比较显然了：

教训

考场上为什么坠机了？

读题

1. 理解为第 道题，随后发现不对；
2. 理解为分配至少 道题，这个难住了我好久；
3. 发现是恰好 道题，想到正解；
4. 忽略题目不一样，忘了乘组合数，一时不知道错在哪里，坠机了。

How

1. 不要去勤于看讨论区的“警示后人”，让自己的“注意到”力下降；
2. 不要看简化的题意，要读原来的，平时让自己赤石考场上才能赤得香；
3. 自己把比较关键的点列出来，尤其是组合数学这种规则很重要的题目；

代码

#include<bits/stdc++.h>
#define LL long long

using namespace std;

const int MAXN = 400;
const LL mod = 1e9 +7;

LL n;
LL ans;

LL C[MAXN][MAXN];
LL f[MAXN][MAXN];

inline LL Pow(LL base, LL expo) {
    base = (base + mod) % mod;
    LL res = 1;
    while (expo) {
        if (expo & 1)
            res = (res * base) % mod;
        base = (base * base) % mod;
        expo >>= 1;
    }
    return res;
}
inline void C_init() {
    C[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
        C[i][0] = 1;
        for (int j = 1; j <= i; ++j)
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
    }
    return;
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n;
    ans = Pow(n, n);
    C_init();
    f[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 (k + i == j)
                    continue;
                f[i][j] = (f[i][j] + f[i - 1][k] * C[j][k]) % mod;
            }
        }
    ans -= f[n][n];
    cout << (ans + mod) % mod;
    return 0;
}