Subsequence Queries | CS Academy #24

コメントつきコード

/*
解法
漸化式で解を表して行列を作ってみる。
行列は添字ごとに異なるので累乗では解けない。
[l, r)の積
A[r-1]A[r-2]...A[l]
の求め方

(1) セグメント木を使って求める
http://yukicoder.me/problems/no/510
の解法
今回の問題ではTLEを食らった
(2)
逆行列を使う
A[r-1]A[r-2]...A[l]
= A[r-1]A[r-2]...A[l]...A[0]inv(A[0])inv(A[1])...inv(A[l-1])
ただし、inv(A[i])は行列A[i]の逆行列とする。
*/

/*
行列Bの左から行列Aを掛けた積を返す
*/
const int MOD = (int)1e9 + 7;
vector<vector<int> > mulMatMod(const vector<vector<int> > &A, const vector<vector<int> > &B) {
    auto n = A.size(), m = A[0].size(), p = B[0].size();
    vector<vector<int> > res(n, vector<int>(p));
    for (int i = 0; i < n; ++i)for (int j = 0; j < p; ++j) for (int k = 0; k < m; ++k)
        res[i][j] = (int)((res[i][j] + (long long)A[i][k] * B[k][j]) % MOD);
    return res;
}

typedef vector<vector<int> > mat;
string S;
int Q;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> S >> Q;
    int N = sz(S);
    mat E(10, vi(10));
    rep(i, 10)E[i][i] = 1;
    vector<mat> AA(N+1, E), BB(N+1, E);
    rep(i, N) {
        int a = S[i] - 'a';
        mat A = E;
        // B=inv(A)
        mat B = E;
        rep(j, 10)A[a][j] = 1;
        // 掛ける順番に注意
        // A[j]A[j-1]...A[0]
        AA[i + 1] = mulMatMod(A, AA[i]);
        /*
        1 0 0 0 0
        1 1 1 1 1
        0 0 1 0 0
        0 0 0 1 0
        0 0 0 0 1
        のように漸化式から作った行列が特殊な形をしているので
        逆行列を簡単に求めることができる。
        */
        rep(r, 10)if (r != a) {
            B[a][r] = (B[a][r] + MOD - 1) % MOD;
        }
        // B[0]B[1]...B[j]
        BB[i + 1] = mulMatMod(BB[i], B);
    }

    mat u(10, vi(1));
    u[9][0] = 1;
    while (Q--) {
        int l, r;
        cin >> l >> r;
        --l;
        // A[l, r) = A[r-1]...A[0]inv(A[0])inv(A[1])...inv(A[l-1])
        mat Alr = mulMatMod(AA[r], BB[l]);
        ll ans = 0;
        rep(i, 9)ans += Alr[i][9];
        cout << ans%MOD << endl;
    }
}