出题人：一只书虫仔 Data：w33z 验题人：MatKave&w33z&一只书虫仔

Description

给定一个 $n$ 行的不规则矩阵，第 $i$ 行的长度为 $a_i$。

现在在上面放 $k$ 个棋子，要保证没有两个棋子在同一行或同一列。

求有多少个放置方案。

$1 \le n,k \le 10^3$，$1 \le a_i \le 10^5$。

Solution

Subtask 1：我会循环把 $a_i$ 加起来！

Subtask 2：我会暴力！

Subtask 3：考虑 dp，定义 $dp_{i,k}$ 为放置到第 $i$ 行时第 $1 \sim i$ 行一共放了 $k$ 个棋子的方案数，分类讨论：

• 这一行不放，可以直接从上一行转移过来，$dp_{i,k}=dp_{i-1,k}$。
• 这一行放，能放的位置个数即为这一行的长度减去已经放了的棋子个数，即从上一行转移过来的时候乘上能放的位置个数即可，$dp_{i,k}=dp_{i-1,k-1} \times (a_i-(k-1))$。

把这两部分加起来即可。

Subtask 4：如果不会考虑 Subtask 3 的“这一行放”的情况的话，这一个 Subtask 可以拯救你。

正解：继续考虑 Subtask 3，如果适用于所有情况，我们有一个问题，如果上一行比这一行要长，有可能上一行放了一些棋子在第 $p$ 列，然而这一行没有 $p$ 个格子那么多。这个问题很好解决，在一开始放的时候从最短的那一行开始放，然后一直放到最长的那一行即可，代码实现的时候排一下序即可。

$\mathcal O(nk)$。

评价：中规中矩的签到题 * 2，给良心的出题人点赞！