用1*2的骨牌覆盖m*n的矩形的有关问题
用1*2的骨牌覆盖m*n的矩形的问题
最近想写个程序算算，用1*2的骨牌覆盖m*n的矩形有多少种不同的方式，Wiki上的公式也很漂亮。
http://en.wikipedia.org/wiki/Domino_tiling#CITEREFKasteleyn1961
但这种计算怎么保证精度呢？还是可以在计算前先把某些项合并？
这是我现在写的一个C#程序，用的double，算稍微大一些的m*n时，就不准了。
http://www.51nod.com/question/index.html#!questionId=316
------解决方案--------------------
你计算不准确的原因是，公式里面求和号上面的 上限 值
是对 m/2 取上整，而你的循环里面 i <= m / 2 只能实现取下整。
正确应该是 (m+1)/2.
同理 （n+1）/2.
------解决方案--------------------
这题我记得有过m<=5，n huge的比赛题的。用的是2^m*log(n)的算法。一看复杂度就知道算法是什么了。
m也大的话那也就理论上有计算可能了。实际上没法算。
------解决方案--------------------
------解决方案--------------------
------解决方案--------------------
------解决方案--------------------
发现自己傻了。证出有理数以后，因为参与运算的都是代数整数，所以直接就出来这个乘积就是代数整数，也就是通常意义上的整数了。
------解决方案--------------------
------解决方案--------------------
------解决方案--------------------
动态规划，从m*(k-1)行到m*k行，记录填满m*(k-1)行时有多少个第k行的格子被覆盖作为状态即可。
可以参考一个更加复杂题目的解答:
http://tieba.baidu.com/p/395424512?pid=4076687686&cid=0#4076687686
------解决方案--------------------
可以参考链接围棋问题的82楼
------解决方案--------------------
------解决方案--------------------
严格的算法是：
使用给定分辨率的整数运算！
如果你非要用实型计算，则需要带方向的截断。
------解决方案--------------------
发现那个公式可以利用第二类切皮雪夫多项式变成一个n阶高斯整数矩列式问题，可以定点计算
------解决方案--------------------
其实变换以后的公式从复杂度上可能还高一些，好处是不需要浮点运算。
原公式是计算所有关于j,k时
4(cos^2((j*pi)/(m+1))+cos^2((k*pi)/(n+1)))
的乘积的1/4次方
上面可以写成||2(i*cos((j*pi)/(m+1))-cos((k*pi)/(n+1)))||^2
我们查看第二类切皮雪夫多项式
U_n(x)=2^n \prod (x - cos((k*pi)/(n+1))
所以结果可以写成
sqrt(||\Prod_{j=1}^m U_n( i*cos((j*pi)/(m+1)))||）
我们记n阶矩阵B_n为除了主对角线边上元素为1，其余为0的矩阵，也就是Bn_ij在|i-j|=1时为1，其余时候为0
那么根据链接第二类切皮雪夫多项式又可以写成det(2x*I_n+B_n),其中I_n为n阶单位阵
所以结果可以写成
sqrt(||det(\Prod_{j=1}^m (2i*cos((j*pi)/(m+1))I_n+B_n))||)
=sqrt(||det(2^m*\Prod_{j=1}^m(i*B_n/2-cos((j*pi)/(m+1))I_n))||)
=sqrt(||det(U_m(i*B_n/2))||)
所以只要我们先计算整系数多项式U_m(x/2),然后将i*B_n代入得出n阶矩阵，然后求行列式的绝对值再开平方即可。
------解决方案--------------------
根据上面算法写了个Pari/Gp程序
最近想写个程序算算，用1*2的骨牌覆盖m*n的矩形有多少种不同的方式，Wiki上的公式也很漂亮。
http://en.wikipedia.org/wiki/Domino_tiling#CITEREFKasteleyn1961
但这种计算怎么保证精度呢？还是可以在计算前先把某些项合并？
这是我现在写的一个C#程序，用的double，算稍微大一些的m*n时，就不准了。
http://www.51nod.com/question/index.html#!questionId=316
------解决方案--------------------
你计算不准确的原因是，公式里面求和号上面的 上限 值
是对 m/2 取上整，而你的循环里面 i <= m / 2 只能实现取下整。
正确应该是 (m+1)/2.
同理 （n+1）/2.
------解决方案--------------------
这题我记得有过m<=5，n huge的比赛题的。用的是2^m*log(n)的算法。一看复杂度就知道算法是什么了。
m也大的话那也就理论上有计算可能了。实际上没法算。
------解决方案--------------------
------解决方案--------------------
------解决方案--------------------
------解决方案--------------------
发现自己傻了。证出有理数以后，因为参与运算的都是代数整数，所以直接就出来这个乘积就是代数整数，也就是通常意义上的整数了。
------解决方案--------------------
------解决方案--------------------
------解决方案--------------------
动态规划，从m*(k-1)行到m*k行，记录填满m*(k-1)行时有多少个第k行的格子被覆盖作为状态即可。
可以参考一个更加复杂题目的解答:
http://tieba.baidu.com/p/395424512?pid=4076687686&cid=0#4076687686
------解决方案--------------------
可以参考链接围棋问题的82楼
------解决方案--------------------
------解决方案--------------------
严格的算法是：
使用给定分辨率的整数运算！
如果你非要用实型计算，则需要带方向的截断。
------解决方案--------------------
发现那个公式可以利用第二类切皮雪夫多项式变成一个n阶高斯整数矩列式问题，可以定点计算
------解决方案--------------------
其实变换以后的公式从复杂度上可能还高一些，好处是不需要浮点运算。
原公式是计算所有关于j,k时
4(cos^2((j*pi)/(m+1))+cos^2((k*pi)/(n+1)))
的乘积的1/4次方
上面可以写成||2(i*cos((j*pi)/(m+1))-cos((k*pi)/(n+1)))||^2
我们查看第二类切皮雪夫多项式
U_n(x)=2^n \prod (x - cos((k*pi)/(n+1))
所以结果可以写成
sqrt(||\Prod_{j=1}^m U_n( i*cos((j*pi)/(m+1)))||）
我们记n阶矩阵B_n为除了主对角线边上元素为1，其余为0的矩阵，也就是Bn_ij在|i-j|=1时为1，其余时候为0
那么根据链接第二类切皮雪夫多项式又可以写成det(2x*I_n+B_n),其中I_n为n阶单位阵
所以结果可以写成
sqrt(||det(\Prod_{j=1}^m (2i*cos((j*pi)/(m+1))I_n+B_n))||)
=sqrt(||det(2^m*\Prod_{j=1}^m(i*B_n/2-cos((j*pi)/(m+1))I_n))||)
=sqrt(||det(U_m(i*B_n/2))||)
所以只要我们先计算整系数多项式U_m(x/2),然后将i*B_n代入得出n阶矩阵，然后求行列式的绝对值再开平方即可。
------解决方案--------------------
根据上面算法写了个Pari/Gp程序