设$f(i,j)$是青蛙已经正确叫出前i个字母，且此时（叫完未跳）位于格子j的概率。
显然初值是$f(0,j)=1/500$，一般地，有$f(i,j)=f(i-1,j+1)\cdot p(j+1,s[i-1])\cdot q(j+1)+f(i-1,j-1)\cdot p(j-1,si-1)\cdot q(j-1)$,
其中$p(n,c)$取$2/3$若n的素性与c的描述相符（P：素数，N：非素数），否则取$1/3$。
q(x)是从x跳到当前格的概率。
递推计算即得结果$199740353/29386561536000$。
from fractions import Fraction
primes={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499}
s="PPPPNNPPPNPPNPN"
f=[[Fraction(0,1)]*501 if i>0 else [Fraction(0)]+[Fraction(1,500)]*500 for i in range(16)]
for i in range(15):
for j in range(1,501):
q=1 if j==1 or j==500 else Fraction(1,2)
p=Fraction(2,3) if (j in primes and s[i]=="P") or (j not in primes and s[i]=="N") else Fraction(1,3)
if j < 500:
f[i+1][j+1]+=f[i][j]*p*q
if j>1:
f[i+1][j-1]+=f[i][j]*p*q
print sum(f[15])
|
