Move on grid [yukicoder No.612] - はまやんはまやんはまやん

解法

まず、少し問題を読み変えておこう。
6^T*pを答えるが、これは条件を満たす座標への遷移の組み合わせ数と等しい（確率pの分母が6^Tであり、分子は組み合わせ数なので）
なので、条件を満たす遷移の組み合わせ数だと考えて解く。
　
次に、ax+by+czという条件について考えてみよう。
これは遷移が6通りあるが、この条件についてのみ考えると+a,-a,+b,-b,+c,-cの遷移だと考えられる。
そう考えてみると、特に今どの座標にいるかは問題ではなくなるため、総和だけ保持してDPできることが分かる。
　
「dp[t][sm] := 時刻tでsm=ax+by+czである組み合わせ数」を計算していこう。
smが負になる可能性があるので、この辺を上手くやる必要がある。
自分はmapを使って高速化をサボった実装をしている。
疎なdpではmapを使うと良いが、今回使うのはあまりおすすめしない。
（mapはO(logN)であるが、体感O(10logN)くらいある。過信してはいけない）
これをやっていって条件を満たす組み合わせ数の総和を答える。

int T, a, b, c, d, e;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> T >> a >> b >> c >> d >> e;
    
    map<int, mint> dp;
    dp[0] = 1;

    rep(t, 0, T) {
        map<int, mint> pd;
        fore(p, dp) {
            pd[p.first + a] += p.second;
            pd[p.first + b] += p.second;
            pd[p.first + c] += p.second;
            pd[p.first - a] += p.second;
            pd[p.first - b] += p.second;
            pd[p.first - c] += p.second;
        }
        swap(dp, pd);
    }

    mint ans = 0;
    fore(p, dp) if (d <= p.first and p.first <= e) ans += p.second;
    cout << ans << endl;
}