結果
問題 | No.1261 数字集め |
ユーザー |
![]() |
提出日時 | 2020-10-16 23:29:13 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3,116 ms / 8,000 ms |
コード長 | 2,167 bytes |
コンパイル時間 | 2,203 ms |
コンパイル使用メモリ | 177,172 KB |
実行使用メモリ | 115,968 KB |
最終ジャッジ日時 | 2024-07-21 04:41:39 |
合計ジャッジ時間 | 148,522 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 94 |
ソースコード
#include <bits/stdc++.h>using namespace std;const long long MOD = 1000000007;array<array<long long, 3>, 3> matmul(array<array<long long, 3>, 3> &A, array<array<long long, 3>, 3> &B){array<array<long long, 3>, 3> ans;for (int i = 0; i < 3; i++){for (int j = 0; j < 3; j++){ans[i][j] = 0;}}for (int i = 0; i < 3; i++){for (int k = 0; k < 3; k++){for (int j = 0; j < 3; j++){ans[i][k] += A[i][j] * B[j][k];}ans[i][k] %= MOD;}}return ans;}array<array<long long, 3>, 3> matexp(array<array<long long, 3>, 3> &A, long long b){array<array<long long, 3>, 3> ans;for (int i = 0; i < 3; i++){for (int j = 0; j < 3; j++){ans[i][j] = i == j;}}while (b > 0){if (b % 2 == 1){ans = matmul(ans, A);}A = matmul(A, A);b /= 2;}return ans;}long long get(vector<int> &A, int M, int a, int b){array<array<long long, 3>, 3> mat;mat[0][0] = A[a - 1] - 1;mat[0][1] = 1;mat[0][2] = 0;mat[1][0] = 0;mat[1][1] = A[b - 1] - 1;mat[1][2] = 1;mat[2][0] = 0;mat[2][1] = 0;mat[2][2] = A.back() - 1;mat = matexp(mat, M - 1);return mat[0][2];}int main(){int N, M;cin >> N >> M;vector<int> A(N, 0);for (int i = 1; i < N; i++){cin >> A[i];}long long ans = 0;vector<vector<int>> prev(N + 1);for (int a = 2; a < N; a++){for (int b = a * 2; b < N; b += a){prev[b].push_back(a);if (N % a == 0 && N % b == 0){ans += get(A, M, a, b);if (ans >= MOD){ans -= MOD;}}}}cout << ans << endl;int Q;cin >> Q;set<int> st;for (int i = 2; i < N; i++){if (N % i == 0){st.insert(i);}}for (int i = 0; i < Q; i++){int X, Y;cin >> X >> Y;if (Y == N){for (int a : prev[X]){ans += get(A, M, a, X);if (ans >= MOD){ans -= MOD;}}st.insert(X);} else {if (st.count(Y)){ans += get(A, M, X, Y);if (ans >= MOD){ans -= MOD;}}}prev[Y].push_back(X);cout << ans << endl;}}