bzoj4563[Haoi2016]放棋子

时间：2016-08-16 23:39:06 阅读：265 评论：0 收藏：0 [点我收藏+]

题意：

给你一个N*N的矩阵，每行有一个障碍，数据保证任意两个障碍不在同一行，任意两个障碍不在同一列。要求你放N枚棋子（障碍的位置不能放棋子），也满足每行只有一枚棋子，每列只有一枚棋子的限制，求有多少种方案。N≤200。

题解：

发现在障碍在什么位置和答案无关。因此可以把棋子摆成左上-右下对角线，然后就是错排问题（一个长度为n的排列，要求每个元素不能放在与自己编号相同的位置上，问有多少种方案满足条件）了。错排公式：f[i]=(f[i-1]+f[i-2])*(i-1)，特别的，f[0]=1，f[1]=0。本弱太懒了，不想写高精度，写了个python，结果因为不会写wa了好几发QAQ

代码：

1 n=int(raw_input())
2 a=1
3 b=0
4 for i in range(2,n+1):
5     c=(a+b)*(i-1)
6     a=b
7     b=c
8 print b

//python的高亮好丑啊！

20160814

bzoj4563[Haoi2016]放棋子

原文：http://www.cnblogs.com/YuanZiming/p/5778008.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)