Problem:


問題文

影の魔女 ELSAMARIA はすべてのものに対して祈りを続ける魔女である．影に捕まったあらゆる命はこの魔女の中に引きずり込まれてしまう．

影は触手のように動き美樹さやかを引きずり込もうと狙っている．美樹さやかはこの魔女に捕まることなく攻撃するために，魔女にとって予測の難しいでたらめな動きをすることを考えた．具体的には，まず頭の中で 1 から N  までの整数を一様な確率で K 個作り，その合計値の距離だけ今の位置から魔女の方向へジャンプする，ということを繰り返すのである．そして魔女の位置に到達した時に攻撃するのである．

さやかと魔女はある一直線上にいるとし，最初魔女は座標 0，さやかは座標 S の位置にいるものとする．また魔女は動かないものとする．何度ジャンプした後に魔女に最初の攻撃を与えることができるだろうか．期待値を求めよ．

入力形式

入力は以下の形式で与えられる．

S\ N\ K

S は最初にさやかがいる座標である．N はさやかが頭の中で作る整数の範囲の上限，K はさやかが 1 回のジャンプに用いる整数の個数である．

出力形式

さやかが魔女の位置に到達するために必要なジャンプの回数の期待値を 1 行に出力せよ．もし何度ジャンプしても魔女の位置へ到達できない，もしくは期待値が有限値に収まらない場合は -1 と出力せよ．

小数点以下何桁でも出力して構わないが，相対誤差あるいは絶対誤差が 10-6 未満になっていなければならない．

制約

-109 ≤ S ≤ 109

1 ≤ N ≤ 10

1 ≤ K ≤ 10

入力値は全て整数である．

入出力例

入力例 1

6 6 1

出力例1

6.00000000

入力例 2

-100 7 5

出力例 2

43.60343043

入力例 3

756434182 9 10

出力例 3

15128783.80867078

Problem Setter: Flat35

Sample input:
6 6 1


Sample output:
6.00000000

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
write = sys.stdout.write

def mul(n, A, B, C):
    for i in range(n):
        for j in range(n):
            C[i][j] = sum(A[i][k] * A[k][j] for k in range(n))
def fast_pow(n, MA, A, k):
    R = [[0]*n for i in range(n)]
    while k:
        if k & 1:
            A = [sum(e*a for e, a in zip(MA[i], A)) for i in range(n)]
        mul(n, MA, MA, R)
        MA, R = R, MA
        k >>= 1
    return A

def solve():
    S, N, K = map(int, readline().split())
    S = abs(S)
    if S == 0:
        write("0\n")
        return
    if N == 1:
        if S % K:
            write("-1\n")
        else:
            write("%.16f\n" % (S // K))
        return
    M = N*K
    dp = [0]*(M+1)
    dp[0] = 1
    for t in range(K):
        for i in range(N*K, -1, -1):
            dp[i] = sum(dp[i-k] for k in range(1, N+1) if i >= k)
    s = sum(dp)
    mat = [[0]*(M+2) for i in range(M+1)]
    mat[0][0] = 1
    for i in range(1, M+1):
        mi = mat[i]
        for j in range(M+1):
            mi[abs(i-j)] -= dp[j]
        mi[i] += s
        for j in range(M+1):
            mi[j] /= s
        mi[M+1] = 1
    for i in range(M+1):
        v = mat[i][i]
        for j in range(M+2):
            mat[i][j] /= v
        for k in range(M+1):
            if k == i:
                continue
            e = mat[k][i]
            for j in range(M+2):
                mat[k][j] -= e * mat[i][j]
    C = [mat[i][M+1] for i in range(M, -1, -1)]
    C[-1] = 1
    if S <= M:
        write("%.16f\n" % C[M-S])
        return

    mat2 = [[0]*(M+1) for i in range(M+1)]
    for i in range(M):
        mat2[0][i] = dp[i+1] / s
    for i in range(M-1):
        mat2[i+1][i] = 1
    mat2[0][M] = mat2[M][M] = 1
    C1 = fast_pow(M+1, mat2, C, S-M)
    write("%.16f\n" % C1[0])
solve()