AtCoder Beginner Contest 275E

E - Sugoroku 4

確率dp.

を と書く．

に対して，

とする．

for を回すとき，移動した回数 を一番外側に持ってくることに注意．

dp では，すでに正しく求まっている計算を利用して次を求めるため．

回目を求めるには， 回目が正しく求まっている必要がある．

逆元を何度も使うので，前計算すると速い．

typedef long long ll;

const ll INFL = 1LL << 60;

using vll = vector<long long>;  using vvll = vector<vll>;

using pll = pair<ll,ll>;

int main() {

    ll n, m, k, q;

    cin >> n >> m >> k;

    mint m_inv = mint(1) / m;

    mint ans;

    dp[0] = 1;

    rep(x, k){

        swap(old, dp);

        rep(i,1005){dp[i] = 0;}

       

        rep(i,n) {

            rep1(s, m){

                ll ni = i + s;

                if(ni > n){

                    ll d = ni - n;

                    ni = n - d; // 折り返した座標

                }

                dp[ni] += old[i] * m_inv;

            }

        }

        ans += dp[n];

    }

   

    cout << ans.val() << endl;

    return 0;

}