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
0 1
1 0
Sample Output
1
这道题竟然考的是高精度，吓到我了……
一开始没读到数据范围还以为是状压裸题，然后一看到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)种方法。（摘自百度百科）
还是挺好玩的。
然后，就是传统的高精度了呗。
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#include <cmath>
#include <map>
#define N 10000
using namespace std;
int n,p=;
struct no
{
int a[N],l;
}f[],c;
no get(int x)
{
no aa;
aa.l=;
aa.a[]=x;
return aa;
}
no jia(no a,no b)
{
memset(c.a,,sizeof(c.a));c.l=;
for(int i=;i<=max(a.l,b.l)+;i++)
{
c.a[i]+=a.a[i]+b.a[i];
c.a[i+]+=c.a[i]/p;
c.a[i]%=p;
}
for(int i=max(a.l,b.l)+;;i--)
{
if(c.a[i])
{
c.l=i;
break;
}
}
return c;
}
no cheng(no a,no b)
{
memset(c.a,,sizeof(c.a));c.l=;
for(int i=;i<=a.l;i++)
{
for(int j=,to=i;j<=b.l;j++,to++)
{
c.a[to]+=a.a[i]*b.a[j];
c.a[to+]+=c.a[to]/p;
c.a[to]%=p;
}
}
for(int i=a.l+b.l+;;i--)
{
if(c.a[i])
{
c.l=i;
break;
}
}
return c;
}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
{
for(int j=;j<=n;j++)
{
int x;
scanf("%d",&x);
}
}
f[].a[]=,f[].l=;
f[].a[]=,f[].l=;
for(int i=;i<=n;i++)
{
f[i]=cheng(get(i-),jia(f[i-],f[i-]));
}
printf("%d",f[n].a[f[n].l]);
for(int i=f[n].l-;i>=;i--)
{
printf("%04d",f[n].a[i]);
}
return ;
}