牛客网 NC205036 答题卡 动态规划

目录

• 牛客网 NC205036 答题卡 动态规划
  • 目录
  • 1. 题目描述
    • 1.1. Limit
    • 1.2. Problem Description
    • 1.3. Input
    • 1.4. Output
    • 1.5. Sample Input
    • 1.6. Sample Output
    • 1.7. Notes
    • 1.8. Source
  • 2. 解读
  • 3. 代码

1. 题目描述

1.1. Limit

Time Limit: 1000 ms

Memory Limit: 131072 kB

1.2. Problem Description

牛牛即将要参加考试，他学会了填答题卡。

可惜他竖着的答题卡填成了横着的 : (

好奇的他想知道对于 $n$ 道题，每道题 $n$ 个选项的答题卡 ( $n \times n$ 的矩阵 )，满足横答题卡和竖答题卡图形一致的方案数有多少种。

注：每道题只能选择一个选项，即 $n \times n$ 的矩阵中只能涂黑 $n$ 个空。求横竖对称的方案数。

---

1.3. Input

第一行给出 $n$。

---

1.4. Output

输出方案数，答案对 $10^9 +7$ 取模

---

1.5. Sample Input

3

1.6. Sample Output

4

1.7. Notes

$$\begin{pmatrix} \blacksquare & \square & \square \\ \square & \blacksquare & \square \\ \square & \square & \blacksquare \\ \end{pmatrix} \Bigg| \begin{pmatrix} \square & \blacksquare & \square \\ \blacksquare & \square & \square \\ \square & \square & \blacksquare \\ \end{pmatrix} \Bigg| \begin{pmatrix} \blacksquare & \square & \square \\ \square & \square & \blacksquare \\ \square & \blacksquare & \square \\ \end{pmatrix} \Bigg| \begin{pmatrix} \square & \square & \blacksquare \\ \square & \blacksquare & \square \\ \blacksquare & \square & \square \\ \end{pmatrix}$$

1.8. Source

牛客网 NC205036 答题卡

---

2. 解读

每当矩阵的维度 $n$ 增加1时，可以分为两种情况计算。

如果矩阵第 $n + 1$ 行的元素坐标为 $(n + 1, n + 1)$，即在矩阵的右下角时，则原先的 $n \times n$ 维矩阵可以取 $f(n)$ 种情况。

如果矩阵第 $n + 1$ 行的元素坐标为 $(n + 1, x)$，$x \in [1, n]$时，则第 $x$ 行的坐标也被确定了，为$(x, n + 1)$，其余的 $n - 1$ 行可以取 $f(n - 1)$ 种情况。

则递推方程为 $f(n + 1) = f(n) + n \times f(n-1)$。

可以化为 $f(n) = f(n - 1) + (n - 1) \times f(n-2)$。

如当 $n$ 从 $2$ 变为 $3$ 时，过程如下所示。

1. $n = 2$ 时，有两种情况。

$$\begin{pmatrix} \blacksquare & \square \\ \square & \blacksquare \\ \end{pmatrix} \Bigg| \begin{pmatrix} \square & \blacksquare \\ \blacksquare & \square \\ \end{pmatrix}$$

1. 当 $n = 3$ 且新增的元素在 $(3, 3)$ 位置时，有 $f(2) = 2$ 种情况

$$\begin{pmatrix} \blacksquare & \square \\ \square & \blacksquare \\ \end{pmatrix} \to \begin{pmatrix} \blacksquare & \square & \square \\ \square & \blacksquare & \square \\ \square & \square & \blacksquare \\ \end{pmatrix} \Bigg| \begin{pmatrix} \square & \blacksquare \\ \blacksquare & \square \\ \end{pmatrix} \to \begin{pmatrix} \square & \blacksquare & \square \\ \blacksquare & \square & \square \\ \square & \square & \blacksquare \\ \end{pmatrix}$$

1. 当 $n = 3$ 且新增的元素在 $(3, x)$，$x \in [1,2]$ 位置时，有 $2 \times f(1) = 2$ 种情况。

$$\begin{pmatrix} \square & \square & \blacksquare \\ \square & \blacksquare & \square \\ \blacksquare & \square & \square \\ \end{pmatrix} \Bigg| \begin{pmatrix} \blacksquare & \square & \square \\ \square & \square & \blacksquare \\ \square & \blacksquare & \square \\ \end{pmatrix}$$

所以 $f(3) = f(2) + 2 \times f(1) = 2 + 2 = 4$。

3. 代码

#include<iostream>
using namespace std;
const int mod=1e9+7;
const int N=1e5+10;
typedef long long ll;
ll n;
ll f[N];
int main() {
    int i;
    cin>>n;
    f[1]=1; f[2]=2;
    for (i=3;i<=n;i++)
        f[i]=(f[i-1]+(i-1)*f[i-2]%mod)%mod;
    cout<<f[n]<<endl;
    return 0;
}

---

联系邮箱：curren_wong@163.com

Github：https://github.com/CurrenWong

欢迎转载/Star/Fork，有问题欢迎通过邮箱交流。