問題概要 長さNの置換pがprime permutationであるとは各iについて最初のi個の数字の中でp[i]がX番目(X=1or素数)に小さいようなものを言う。各iについて長さiのprime permutationがいくつあるか求める問題。 解法 p(i)をi以下の素数の個数とする。今、ans[i+1…

問題概要 長さN,M( 解法 末尾がn文字一致している状態から必要な個数の期待値をE[n]とする。failure linkを用いて連立一次方程式を立式できる。このとき、各iについてE[i]=P[i]+Q[i]*E[0]とおくことによってE[N]=P[N]+Q[N]*E[0]までDPで計算できる。あとはE[…

結果。 4/5完。接続不良でペナルティにほとんど意味が無い。SPOJ使う限りこうなるのは避けられない気がする。