[Haoi2016]放棋子题解

4563: [Haoi2016]放棋子

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 440 Solved: 285
[Submit][Status][Discuss]

Description

给你一个N*N的矩阵，每行有一个障碍，数据保证任意两个障碍不在同一行，任意两个障碍不在同一列，要求你在

这个矩阵上放N枚棋子（障碍的位置不能放棋子），要求你放N个棋子也满足每行只有一枚棋子，每列只有一枚棋子

的限制，求有多少种方案。

Input

第一行一个N，接下来一个N*N的矩阵。N<=200,0表示没有障碍，1表示有障碍，输入格式参考样例

Output

一个整数，即合法的方案数。

Sample Input

2
0 1
1 0

Sample Output

　　这道题竟然考的是高精度，吓到我了……

　　一开始没读到数据范围还以为是状压裸题，然后一看到N<=200，吓一跳，然后开始琢磨动归方程，于是乎，一开始就错了的我走上了一条不归路。

　　最后实在没辙，看了一眼题解，好吧，我输了。

　　这道题我们可以分析为错排问题：一共 1～n n个数，对于任意数x都不在第x个位置上有多少方案数。

　　为什么这么说呢？我们可以注意到，既然每一行每一列有且只有一个障碍，那么，每一行障碍的位置对于答案没有任何实际影响，如果我们按照每一行障碍的位置对行进行排序的话就转化成了第i行的棋子不能出现在第i个位置的问题，也就是我们上面说的错排问题了。

　　那么错排问题的公式是什么呢？

　　　　f[i]=f[i-1]*(i-1)+f[i-2]*(i-1)

　　　　原理：

　　　　　　第一步，把第n个元素放在一个位置，比如位置k，一共有n-1种方法；

　　　　　　第二步，放编号为k的元素，这时有两种情况：⑴把它放到位置n，那么，对于剩下的n-1个元素，由于第k个元素放到了位置n，剩下n-2个元素就有f(n-2)种方法；⑵第k　　　　个元素不把它放到位置n，这时，对于这n-1个元素，有f(n-1)种方法。（摘自百度百科）

　　还是挺好玩的。

　　然后，就是传统的高精度了呗。

 1 #include <iostream>
 2 #include <cstdlib>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <queue>
 6 #include <algorithm>
 7 #include <cmath>
 8 #include <map>
 9 #define N 10000
10 using namespace std;
11 int n,p=10000;
12 struct no
13 {
14     int a[N],l;
15 }f[205],c;
16 no get(int x)
17 {
18     no aa;
19     aa.l=1;
20     aa.a[1]=x;
21     return aa;
22 }
23 no jia(no a,no b)
24 {
25     memset(c.a,0,sizeof(c.a));c.l=0;
26     for(int i=1;i<=max(a.l,b.l)+2;i++)
27     {
28         c.a[i]+=a.a[i]+b.a[i];
29         c.a[i+1]+=c.a[i]/p;
30         c.a[i]%=p;
31     }
32     for(int i=max(a.l,b.l)+2;;i--)
33     {
34         if(c.a[i])
35         {
36             c.l=i;
37             break;
38         }
39     }
40     return c;
41 }
42 no cheng(no a,no b)
43 {
44     memset(c.a,0,sizeof(c.a));c.l=0;
45     for(int i=1;i<=a.l;i++)
46     {
47         for(int j=1,to=i;j<=b.l;j++,to++)
48         {
49             c.a[to]+=a.a[i]*b.a[j];
50             c.a[to+1]+=c.a[to]/p;
51             c.a[to]%=p;
52         }
53     }
54     for(int i=a.l+b.l+2;;i--)
55     {
56         if(c.a[i])
57         {
58             c.l=i;
59             break;
60         }
61     }
62     return c;
63 }
64 int main()
65 {
66     scanf("%d",&n);
67     for(int i=1;i<=n;i++)
68     {
69         for(int j=1;j<=n;j++)
70         {
71             int x;
72             scanf("%d",&x);
73         }
74     }
75     f[1].a[1]=0,f[1].l=1;
76     f[2].a[1]=1,f[2].l=1;
77     for(int i=3;i<=n;i++)
78     {
79         f[i]=cheng(get(i-1),jia(f[i-1],f[i-2]));
80     }
81     printf("%d",f[n].a[f[n].l]);
82     for(int i=f[n].l-1;i>=1;i--)
83     {
84         printf("%04d",f[n].a[i]);
85     }
86     return 0;
87 }

View Code