408. Admissible paths through a grid http://projecteuler.net/problem=408 我們稱整數點 ( x , y ) 為「不可容許的點」，如果他的 x、y 還有 x + y 都是正完全 平方數。舉例來說，(9,16) 就是不可容許的點，但 (0,4)、(3,1)、(9,4) 就不是。 再來想一條路徑，起點是 ( x_1 , y_1 )，終點是 ( x_2 , y_2)，走的方法只能用一單位 往北或是一單位往東。如果某條路徑，途中沒有經過不可容許的點，我們則稱這條路徑為 「可容許的路徑」。 使 P(n) 為 (0,0) 到 (n,n) 中可容許的路徑的數量。我們知道 P(5) = 252，P(16) = 596994440，P(1000) mod 1000000007 = 341920854。 請求出 P(10000000) mod 1000000007。 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 125.224.8.123