题目传送门
这题是我在洛谷上搜索“二分图”搜出来的题目……
这题的正解是错排公式+高精度。说实话，错排问题和二分图好像还是有一点点的关系的……
首先，这题中的n个障碍显然没有什么卵用，把所有的障碍都放到n*n的矩形的对角线上显然对原问题的求解没有什么影响。
然后，设f[i]为i*i的矩形的错排方案数，我们提取1~i行和1~i列，建立一个二分图，显然对于每一行有i-1中连接方案。
这样我们就把原问题转化成了求f[n]，也就是求n*n的矩形转化成的二分图的完美匹配方案数。
接着，我们考虑f[i]的计算方法。请各位读者YY一下：
1.若第j行连接到第k列，第k行连接到第j行，那么f[i]就应该等于f[i-2]*(n-1)。
2.若第j行连接到第k列，而第k行不连接到第j行，那么f[i]就应该等于f[i-1]*(n-1)。
综上所述，我们得到了错排公式：f[i]=(f[i-1]+f[i-2])*(n-1)。
有了以上的公式，我们求解这道题就非常方便了：只要套公式就行了。
注意：f[i]可能很大，需要打高精度。
附上AC代码：
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct note{ int a[1010],len; void clear(){ memset(a,0,sizeof a);len=0; } void print(){ for (int i=len; i>=1; --i) printf("%d",a[i]); return; } }f[2010]; int n; note jia(note p,note q){ note o;o.clear();o.len=max(p.len,q.len); for (int i=1; i<=o.len; ++i) o.a[i]+=p.a[i]+q.a[i],o.a[i+1]+=o.a[i]/10,o.a[i]%=10; if (o.a[o.len+1]) ++o.len; return o; } void cheng(note& u,int k){ for (int i=1; i<=u.len; ++i) u.a[i]*=k; for (int i=1; i<=u.len; ++i) u.a[i+1]+=u.a[i]/10,u.a[i]%=10; while (u.a[u.len+1]) ++u.len; return; } int main(void){ scanf("%d",&n); f[1].len=1,f[2].a[1]=1,f[2].len=1; for (int i=3; i<=n; ++i) cheng(f[i]=jia(f[i-1],f[i-2]),i-1); f[n].print(); return 0; }