[蓝桥杯 2021 省 AB2] 国际象棋

Luogu

IDLGP8756

Time1000ms

Memory128MB

DifficultyP5

2021蓝桥杯省赛状压 DP

众所周知， “八皇后” 问题是求解在国际象棋棋盘上摆放 $8$ 个皇后，使得两两之间互不攻击的方案数。已经学习了很多算法的小蓝觉得 “八皇后” 问题太简单了，意犹末尽。作为一个国际象棋迷，他想研究在 $N \times M$ 的棋盘上，摆放 $K$ 个马，使得两两之间互不攻击有多少种摆放方案。由于方案数可能很大，只需计算答案除以 $1000000007$（即 $10^{9}+7$）的余数。如下图所示，国际象棋中的马摆放在棋盘的方格内，走 “日” 字, 位于 $(x, y)$ 格的马（第 $x$ 行第 $y$ 列）可以攻击 $(x+1, y+2),(x+1, y-2),(x-1, y+2),(x-1, y-2),(x+2, y+1),(x+2, y-1),(x-2, y+1),(x-2, y-1)$ 共 $8$ 个格子。 ![](https://luogu.oss-cn-hangzhou.aliyuncs.com/upload/vjudge_pic/lanqiao/2022_09_29_68f9131d5c14c1f27e68g-12.jpg) ## Input 输入一行包含三个正整数 $N, M, K$, 分别表示棋盘的行数、列数和马的个数。 ## Output 输出一个整数，表示摆放的方案数除以 $1000000007$（即 $10^{9}+7$）的余数。 [samples] ## Note 对于 $5 \%$ 的评测用例, $K=1$; 对于另外 $10 \%$ 的评测用例, $K=2$; 对于另外 $10 \%$ 的评测用例, $N=1$; 对于另外 $20 \%$ 的评测用例, $N, M \leq 6, K \leq 5$; 对于另外 $25 \%$ 的评测用例, $N \leq 3, M \leq 20 ， K \leq 12$; 对于所有评测用例, $1 \leq N \leq 6,1 \leq M \leq 100,1 \leq K \leq 20$。蓝桥杯 2021 第二轮省赛 A 组 I 题（B 组 J 题）。

Samples

Input #1

1 2 1

Output #1

Input #2

4 4 3

Output #2

Input #3

3 20 12

Output #3

914051446

API Response (JSON)

{
  "problem": {
    "name": "[蓝桥杯 2021 省 AB2] 国际象棋",
    "description": {
      "content": "众所周知， “八皇后” 问题是求解在国际象棋棋盘上摆放 $8$ 个皇后，使得两两之间互不攻击的方案数。已经学习了很多算法的小蓝觉得 “八皇后” 问题太简单了，意犹末尽。作为一个国际象棋迷，他想研究在 $N \\times M$ 的棋盘上，摆放 $K$ 个马，使得两两之间互不攻击有多少种摆放方案。由于方案数可能很大，只需计算答案除以 $1000000007$（即 $10^{9}+7$）的余数。 如下",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8756"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "众所周知， “八皇后” 问题是求解在国际象棋棋盘上摆放 $8$ 个皇后，使得两两之间互不攻击的方案数。已经学习了很多算法的小蓝觉得 “八皇后” 问题太简单了，意犹末尽。作为一个国际象棋迷，他想研究在 $N \\times M$ 的棋盘上，摆放 $K$ 个马，使得两两之间互不攻击有多少种摆放方案。由于方案数可能很大，只需计算答案除以 $1000000007$（即 $10^{9}+7$）的余数。\n\n如下...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments