求C题分析过程

打表

s1 =1 s2 = s1+1 x s0 s3 = s2 + (3-1) x s1 s4 = s3 + (4 - 1) x s2 s5 = s4 + (5 - 1) x s3 以这个思路，最后递归的总時間太長......🙃

有点组合数学那味。计数问题最重要的就是对集合的划分要不重不漏吧。这个题我是这么划分的： 第一行一定要填一个位置。所以枚举第一行填的位置。 设f(x , k)为x*x的网格，第一行填涂第k位的方案数。那么答案就为f(x) = f(x,1) + ... + f(x , x). 若k = 1.那么第一行第一列都不能填了，问题化简成f(x - 1). k != 1 时，根据对称的要求，位置 (1 , k) 与 (k , 1) 都被填了.那么行和列都会少两个项。剩下来x - 2 行 x - 2 列。所以问题化简成f(x - 2)  .. 推荐画画图就出来了.  所以递推式为: f(x) = f(x - 1) + (x - 1) * f(x - 2).  然而比赛的时候并没有这么做细的分析。。。画画图就找得到递推式了.

建议看每日一题4.29日的，那个题目就是这个的加强版，他每日一题讲的很详细的，这个题就只是点的可能性只有独立一点和二元无向环，那个每一题是多元环，分析方法是一样的

把”对称“形式化表示一下，其实就是选两个点去匹配，然后递推统计匹配的方案数就行。

https://ac.nowcoder.com/discuss/421720?type=101 题解里有很详细的分析