Algorithm@Zx.MYS

POJ月赛，不过我是快结束的时候才知道有月赛的，过去把题都看了一下，然后挑了几水道做，难的等待有空慢慢啃，麻烦的模拟忽略= =

pku/poj 3740 Easy Finding 题解/解题报告：

完全覆盖问题，Dancing Links搞定。不过本题数据规模预处理+2^m的搜索也行

pku/poj 3742 Equivalent Polynomial 题解/解题报告：

二项式定理+解方程组+高精度运算题。这题时间很紧，高斯消元n^3会超时，不过由于方程组的特殊性（三角阵）不需要高斯消元，n^2即可。另外这题很囧，C++似乎要用FFT的高精度乘法才能过，反正我是不会写。用Java可以水过，因为Java的BigInteger类乘法用的就是FFT 2010-3-6 UPDATE:Java的BigInteger类并非用了FFT，只是很普通的压位而已，看来是因为Java时限过宽的原因。

pku/poj 3740 Scout YYF I 题解/解题报告：

DP。设f[i]表示跑到第i个地雷后一个格子的几率，d[i]为第i个地雷的位置，p(i)表示从第一格走到第i格的概率（注意不是参数p），则f[i]=f[i-1]*p((d[i]-1)-(d[i-1]+1))*(1-p)。p((d[i]-1)-(d[i-1]+1))即从第i-1个地雷后一格起始走到第i个地雷前一格的概率。关键是p(i)的计算。懒的推公式的可以用矩阵乘法，设p(i)是走到第i格的概率，则[p(i) p(i+1)] * ([0 (1-p)][1 p])=[p(i+1) p(i+2)] （打不了公式= =，([0 (1-p)][1 p])是一个矩阵的两行），然后快速幂即可。或者推公式，根据p(i+1)=p(i)*p+p(i-1)*(1-p)得出p(i+1)-p(i)=(p-1)(p(i)-p(i-1))得出p(i+1)-p(i)的通项公式（等比数列）然后再由p2-p1的首项得出p(i)的通项公式，这样就可以在o(1)的时间内算出走任意多格的概率，然后逐个地雷递推即可

Relate Posts:

• 置换群和Polya定理：poj1026,poj1286,poj2409,poj3270