[COGS 1517] 放国王

题目描述

原题地址：COGS

思路

对于此题，先考虑一个弱化版的题目：

• 在$n\times n$的棋盘上放国王，有多少种方法？

[COGS 1516] 棋盘上的车

题目描述

原题地址：COGS

思路一

乘法原理水过，计算$n!$即可，复杂度$O(n)$

思路二

DP方程

每次放置一枚棋子，一行一行放，可以用一个二进制数表示状态，如$(0010011)_2$表示第一、二、五列已放棋子。

设$f(n)$是放置$n$枚棋子的方案数，可以知道，$f((0010011)_2)=f((0000011)_2)+f((0010001)_2)+f((0010010)_2)$，类似地，我们可以推出方程：