{"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如下图所示，国际象棋中的马摆放在棋盘的方格内，走 “日” 字, 位于 $(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$ 个 格子。\n\n![](https://luogu.oss-cn-hangzhou.aliyuncs.com/upload/vjudge_pic/lanqiao/2022_09_29_68f9131d5c14c1f27e68g-12.jpg)\n\n## Input\n\n输入一行包含三个正整数 $N, M, K$, 分别表示棋盘的行数、列数和马的个数。\n\n## Output\n\n输出一个整数，表示摆放的方案数除以 $1000000007$（即 $10^{9}+7$）的余数。\n\n[samples]\n\n## Note\n\n对于 $5 \\%$ 的评测用例, $K=1$;\n\n对于另外 $10 \\%$ 的评测用例, $K=2$;\n\n对于另外 $10 \\%$ 的评测用例, $N=1$;\n\n对于另外 $20 \\%$ 的评测用例, $N, M \\leq 6, K \\leq 5$;\n\n对于另外 $25 \\%$ 的评测用例, $N \\leq 3, M \\leq 20 ， K \\leq 12$;\n\n对于所有评测用例, $1 \\leq N \\leq 6,1 \\leq M \\leq 100,1 \\leq K \\leq 20$。 \n\n蓝桥杯 2021 第二轮省赛 A 组 I 题（B 组 J 题）。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8756","tags":["2021","蓝桥杯省赛","状压 DP"],"sample_group":[["1 2 1","2"],["4 4 3","276"],["3 20 12","914051446"]],"created_at":"2026-03-03 11:09:25"}}