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; } }