题目大意

将 $N$ 道不同的题目分配给 $N$ 个选手，每个选手可以分配到 $0$ 到 $N$ 道题。如果第 $i$ 个选手恰好分配到 $i$ 道题，他就会开心。求至少有一个选手开心的分配方案数，结果对 $10^9+7$ 取模。

问题分析

关键观察

1. 总方案数：每道题可以分配给任意一个选手，因此总分配方案数为 $N^N$
2. 条件约束：第 $i$ 个选手开心的条件是获得恰好 $i$ 道题
3. 至少条件："至少一个选手开心"的补集是"所有选手都不开心"

问题转化

使用补集转化：

$$\text{答案} = \text{总方案数} - \text{无人开心的方案数}$$

算法设计

方法一：动态规划（推荐）

核心思想：使用动态规划计算无人开心的方案数。

状态设计

设 $dp[i][j]$ 表示考虑前 $i$ 个选手，已经分配了 $j$ 道题目，且所有前 $i$ 个选手都不开心的方案数。

状态转移

对于第 $i$ 个选手，他可以分配到 $k$ 道题，但要满足 $k \neq i$（因为如果分配到 $i$ 道题就会开心）：

$$dp[i][j] = \sum_{k=0}^{\min(j, N)} [k \neq i] \times \binom{j}{k} \times dp[i-1][j-k] $$

其中 $\binom{j}{k}$ 是从 $j$ 道题中选出 $k$ 道分配给第 $i$ 个选手的组合数。

初始化

• $dp[0][0] = 1$（没有选手，没有题目，只有一种方案）
• $dp[0][j] = 0$ for $j > 0$

最终答案

$$\text{答案} = N^N - dp[N][N]$$

方法二：容斥原理

核心思想：直接计算至少一个选手开心的方案数。

容斥公式

设 $A_i$ 表示第 $i$ 个选手开心的事件，则：

$$\left| \bigcup_{i=1}^N A_i \right| = \sum_{k=1}^N (-1)^{k-1} \sum_{1 \leq i_1 < \cdots < i_k \leq N} |A_{i_1} \cap \cdots \cap A_{i_k}| $$

交集计算

如果指定 $k$ 个选手 $i_1, i_2, \ldots, i_k$ 都开心，那么：

• 这 $k$ 个选手分别获得 $i_1, i_2, \ldots, i_k$ 道题
• 总共分配了 $S = i_1 + i_2 + \cdots + i_k$ 道题
• 如果 $S > N$，则方案数为 $0$
• 否则，方案数为 $\binom{N}{i_1, i_2, \ldots, i_k} \times (N-S)^{N-S}$

其中 $\binom{N}{i_1, i_2, \ldots, i_k}$ 是多组合数。

方法三：生成函数

核心思想：使用指数生成函数表示分配方案。

每个选手的生成函数为：

$$F_i(x) = \sum_{k=0, k\neq i}^N \frac{x^k}{k!}$$

无人开心的方案数为：

$$N! \times [x^N] \prod_{i=1}^N F_i(x)$$

其中 $[x^N]$ 表示提取 $x^N$ 的系数。

实现细节

动态规划实现

// 伪代码
const int MOD = 1e9 + 7;

// 预处理组合数
vector<vector<int>> C(N+1, vector<int>(N+1));
for (int i = 0; i <= N; i++) {
    C[i][0] = C[i][i] = 1;
    for (int j = 1; j < i; j++) {
        C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
    }
}

// 动态规划
vector<vector<int>> dp(N+1, vector<int>(N+1, 0));
dp[0][0] = 1;

for (int i = 1; i <= N; i++) {
    for (int j = 0; j <= N; j++) {
        for (int k = 0; k <= min(j, N); k++) {
            if (k != i) {  // 第i个选手不能拿到恰好i道题
                dp[i][j] = (dp[i][j] + 1LL * C[j][k] * dp[i-1][j-k]) % MOD;
            }
        }
    }
}

// 计算总方案数
long long total = 1;
for (int i = 0; i < N; i++) {
    total = total * N % MOD;
}

// 最终答案
int ans = (total - dp[N][N] + MOD) % MOD;

复杂度分析

动态规划方法

• 时间复杂度：$O(N^3)$
• 空间复杂度：$O(N^2)$
• 对于 $N \leq 350$，完全可行

容斥原理方法

• 时间复杂度：$O(2^N \times \text{多项式时间})$，对于 $N \leq 350$ 不可行
• 仅适用于小数据

关键洞察

算法选择

• 推荐动态规划方法：对于 $N \leq 350$，$O(N^3)$ 的DP是可接受的
• 容斥原理在 $N$ 较大时指数级增长，不可行

优化技巧

1. 组合数预处理：预先计算所有需要的组合数
2. 模运算优化：使用 long long 避免中间结果溢出
3. 空间优化：DP数组可以滚动优化到 $O(N)$ 空间

边界情况

1. $N = 1$：只有一种分配方案（所有题给第一个选手），他一定开心
2. $N = 2$：手动验证与样例一致
3. 注意模运算的负数处理：$(a - b + \text{MOD}) \% \text{MOD}$

扩展思考

更高效的算法

对于更大的 $N$，可以考虑：

1. 生成函数+FFT：使用快速傅里叶变换加速生成函数乘法
2. 多项式插值：利用问题的组合结构设计更高效的算法

问题变种

1. 恰好 $k$ 个选手开心：使用包含排斥原理或生成函数
2. 题目相同：如果题目相同，则使用整数划分计数

总结

本题是一个经典的组合计数问题，核心在于使用动态规划计算不满足条件的方案数，然后通过补集转化得到答案。动态规划方法充分利用了 $N \leq 350$ 的约束，提供了简洁有效的解决方案。

关键点：理解补集转化的思想，设计合适的DP状态，以及正确处理组合数的计算和模运算。