mayoko’s diary

プロコンとかいろいろ。

AtCoder Regular Contest 027 D - ぴょんぴょんトレーニング

解法

解説を参考にしました。

www.slideshare.net

h[i] の値は 10 以下であるので, dp[t] = (t 番目の石までたどり着く方法は何通りあるのか) というのは, t より前の 10 個の dp の値 dp[s], dp[s-1], ..., dp[s-9] が分かればそれをもとに計算することが出来ます。
もう少し詳しく言うと, dp[t] は dp[s], ..., dp[s-9] の線形和で表すことが出来ます。これを考えると,
(dp[t], dp[t-1], ..., dp[t-9]) = (dp[s], dp[s-1], ..., dp[s-9]) * A (A は 10*10 の行列) と書けることがわかります。

t-s の値が少なければ, この A の各要素は, dp[s-i] からスタートした dp をそれぞれ求めることで O(10*(t-s)) で求められます。これを利用して平方分割をします。

前計算で, 石 p*B から 石 (p+1)*B (B は N の平方根)への変換行列をすべて前計算しておきます。
で, 各クエリに対しては, 最初に s 以上で B の倍数の石 l, t 以下で B の倍数の石 r をまず探します。で, s -> l は直接変換行列を計算, l -> r は前計算した変換行列を掛けあわせて計算, r -> t は直接変換行列を計算, して dp[t] を求めます。

計算を高速化するために, 行列同士を何回も掛け算するんじゃなくて 行列 * ベクトルを繰り返し計算しています。

あと, (dp[t], dp[t-1], ..., dp[t-9]) = (dp[s], dp[s-1], ..., dp[s-9]) * A を満たす変換行列を求める時, 例えば dp[t] への経路を求める時, s-3 -> s -> ... というような経路を許してはいけません(この計算は s からの経路が担当しているので)。初手は s+1 以上になるような経路になるようなものだけ計算するようにします。

typedef long long number;
typedef vector<number> vec;
typedef vector<vec> matrix;

const int MOD = 1e9+7;

// O( n^3 )
matrix mul(const matrix &A, const matrix &B) {
    matrix C(A.size(), vec(B[0].size()));
    for (int i = 0; i < (int)C.size(); ++i)
        for (int j = 0; j < (int)C[i].size(); ++j)
            for (int k = 0; k < (int)A[i].size(); ++k) {
                C[i][j] += A[i][k] * B[k][j];
                C[i][j] %= MOD;
            }
    return C;
}
// O( n^2 )
vec mul(const matrix &A, const vec &x) {
    vec y(A.size());
    for (int i = 0; i < (int)A.size(); ++i)
        for (int j = 0; j < (int)A[0].size(); ++j)
            (y[i] += (A[i][j] * x[j])%MOD) %= MOD;
    return y;
}

const int MAXN = 320000;
const int MAXH = 10;
const int B = 550;
int h[MAXN];
matrix memo[MAXN/B];

matrix calc(int s, int t) {
    matrix ret(10, vec(10));
    for (int i = 0; i < 10; i++) {
        int start = s-i;
        if (start < 0) continue;
        vector<int> dp(t-s+10);
        int sz = dp.size();
        for (int k = 1; k <= h[start]; k++) if (s < start+k && start+k <= t) dp[start+k-(s+1)] = 1;
        for (int i = 0; i < sz; i++) {
            if (i+s+1 > t) break;
            for (int k = 1; k <= h[i+s+1]; k++) {
                if (i+k >= sz) break;
                (dp[i+k] += dp[i]) %= MOD;
            }
        }
        for (int j = 0; j < 10; j++) {
            if (t-j <= s) {
                if (t-j == start) ret[10-1-i][10-1-j]++;
                continue;
            }
            ret[10-1-i][10-1-j] = dp[t-j-(s+1)];
        }
    }
    return ret;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) cin >> h[i];
    for (int i = 0; i < N/B; i++) {
        memo[i] = calc(i*B, (i+1)*B);
    }
    int D;
    cin >> D;
    while (D--) {
        int s, t;
        cin >> s >> t;
        s--; t--;
        int l = s/B + (s%B ? 1 : 0), r = t/B;
        vec v(10);
        v[9] = 1;
        if (l < r) {
            v = mul(calc(r*B, t), v);
            for (int i = r-1; i >= l; i--) {
                v = mul(memo[i], v);
            }
            v = mul(calc(s, l*B), v);
        } else {
            v = mul(calc(s, t), v);
        }
        cout << v[9] << endl;
    }
    return 0;
}