Project Euler

■118
再帰で全順列を生成し，その順列を適当に分割して条件を満たすか判定するだけ．簡単な枝刈りを入れれば高速．

■120
(a-1)ⁿ+(a+1)ⁿ mod a²
は結局，
2|n:
⇒2
o.w.:
⇒2an mod a²
になる．
また，2an mod a²の周期は(多分)高々aなので，計算量は一気に減る．というわけで，全探索で間に合う．

■121
[ターン数][青の個数]でDP
初期条件は，[0][0]=1．
jターン目に青(赤)を引く確率をP_青(赤)(j)とすると，
P_青(j)=1/(j+1)
P_赤(j)=j/(j+1)
となり，更新式は，
dp[j][0]=dp[j-1][0]*P_青(j)
dp[j][i]=dp[j-1][i-1]*P_青(j)+dp[j-1][i]*P_赤(j) (i>0)

■123
120のaが素数バージョン．エラトステネスの篩で適当に素数を生成しておく．