「HLOI2015」Color

题目描述

魔法世界的庆典就要到了，大法师交给 Chavo 好多好多魔法丝带，要求 Chavo 为它们涂上五彩斑斓的颜色。Chavo 把一条丝带等分成 m 段，将连续的几段涂上一种颜色。她有 n 种不同颜色的颜料，而且她会使用每一种颜色一次且仅一次。某一次涂色可能会覆盖掉之前已经涂上的颜色，但是她不会让一种颜色完全覆盖掉另外一种颜色。现在 Chavo 想知道，她有多少种不同的方案为一条丝带涂色？结果要对 10⁹ + 7 取模后输出。

设颜色 A 的起点为 L₁，终点为 R₁，颜色 B 的起点为 L₂，终点为 R₂，当 L₁ ≤ L₂ ≤ R₂ ≤ R₁ 时，颜色 A 完全覆盖颜色 B 。每一种方案包含 n 对 L_i 和 R_i，每一对 L_i 和 R_i 代表一次涂色的起点和终点（其中 1 ≤ L_i ≤ R_i ≤ m）。

两种方案不一样当且仅当一种方案里的某一次涂色的起点和终点在另外一种方案里不存在。

输入

只有一行输入整数 n 和 m。

输出

输出一行带有一个整数代表有多少种画法满足题意，结果要对 10⁹ + 7 取模后输出。

样例输入

2 3

样例输出

6

样例说明

6 种情况为：

数据范围及约定

对于 30% 的数据，1 ≤ n, m ≤ 10；

对于 60% 的数据，1 ≤ n, m ≤ 100；

对于 100% 的数据，1 ≤ n × m ≤ 10⁵。

时间限制与空间限制

时间限制：2000ms，空间限制：128MB

题解

由题意可知，对于任意两段颜色来说，设起点分别为 L₁, L₂，终点分别为 R₁, R₂。

若 L₁ = L₂，则无论 R₁, R₂ 大小关系如何，必定一段颜色覆盖另一段，不满足题意。同理 R₁ ≠ R₂。于是可以知道每一个位置最多是一种颜色的起点，一种颜色的终点。

令 L₁ < L₂（反之也是一样），若 R₁ > R₂，则第一段颜色覆盖第二段颜色，所以必有 R₁ < R₂ 对任意两段颜色都成立，则对所有颜色都成立。

所以有 L₁ < L₂ < … < L_n，则必有 R₁ < R₂ < … < R_n，且 L₁ ≤ R₁, L₂ ≤ R₂, …, L_n ≤ R_n。由此可知，某个起点 L_i 所对应的 R_i 与其位置无关，仅与已经确定的 R_i 的个数有关。故考虑以下动态规划状态。

f(k,i,j) 代表在已经确定前 k − 1 个格子中有 i 个起点和 j 个终点，第 k 个格子为确定四种状态之一：起点，终点，既是起点又是终点，不是起点也不是终点。

时间复杂度为 𝒪(n²m)。

对于 n × m ≤ 10⁵，考虑到如果 n > m，则无解，故 n ≤ m，由此推出 n² ≤ n × m ≤ 10⁵，则 n < 333，则 n²m ≤ 3.33 × 10⁷，可以在时限内运行完。因为一个格子的状态只与上一个格子的状态有关，可以用滚动数组优化内存空间。

代码见这里。