注:以下的 \(i\) 不在下标时均代表虚数单位,\([n]=\{1,2,...,n\}\)。
首先把格子当成点,连一个图出来:上下格子连向上的边,左右格子交替连向左/向右的边。这样求完美匹配方案数即可。这样假设搞出来的邻接矩阵是 \(S\)。
那么 \(ans=Pf(S)=\sqrt{\det S}\)。通过对行的缩放操作(即初等变换),可以得到另一个更便于计算的矩阵:如果两个格子竖着相邻,矩阵值为 \(i\),否则横着为 \(1\),不相邻是 \(0\)。这是 \((m\times n)^2\) 的矩阵。
考虑在 \(\C\) 上的线性空间由 \([m]\times [n]\to \C\) 的函数构成。这显然是 \(nm\) 维的。那么一个线性变换 \(L\) 的矩阵就是我们需要的:
\[(Lf)(x,y)=f(x+1,y)+f(x-1,y)+if(x,y-1)+if(x,y+1) \]越界就是 \(0\)。
考虑如下恒等式:
\[\sin((k-1)\theta)+\sin((k+1)\theta)=2\sin(k\theta)\cos\theta \]从而,考虑特征函数(对于 \((a,b)\)) \(f=\{\sin\frac{a\pi x}{n+1}\sin \frac{b\pi y}{m+1}\}_{1\le a\le m,1\le b\le n}\)。根据上面的恒等式,我就有
\[Lf=(2\cos\frac{a\pi}{n+1}+2i\cos \frac{b\pi}{m+1})f \]而对于所有 \(a,b\) 这个 \(f\) 应该是一组基。这样我们就构造出了特征值。
而
\[\det L=\prod \lambda_i=2^{ab}\prod_{a=1}^m\prod_{b=1}^n\left(\cos\frac{a\pi}{n+1}+i\cos \frac{b\pi}{m+1}\right) \]对其开根就得到了(设 \(2\mid m\),否则均奇数无解)
\[4^{\frac m2\lfloor \frac n2\rfloor}\prod_{a=1}^{\lfloor \frac n2\rfloor}\prod_{b=1}^{\frac m2}\left(\cos^2\frac{a\pi}{n+1}+\cos^2 \frac{b\pi}{m+1}\right)^2 \] 标签:cos,prod,frac,718,1x2,le,骨牌,pi,sin From: https://www.cnblogs.com/british-union/p/18310247/718-gupai