結果
問題 | No.2017 Mod7 Parade |
ユーザー | ぷら |
提出日時 | 2022-07-22 21:42:31 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,330 ms / 2,000 ms |
コード長 | 1,894 bytes |
コンパイル時間 | 2,186 ms |
コンパイル使用メモリ | 208,560 KB |
実行使用メモリ | 6,724 KB |
最終ジャッジ日時 | 2023-09-17 09:25:20 |
合計ジャッジ時間 | 18,320 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,376 KB |
testcase_01 | AC | 2 ms
4,376 KB |
testcase_02 | AC | 1 ms
4,376 KB |
testcase_03 | AC | 1,041 ms
6,152 KB |
testcase_04 | AC | 699 ms
4,928 KB |
testcase_05 | AC | 514 ms
4,544 KB |
testcase_06 | AC | 1,154 ms
6,472 KB |
testcase_07 | AC | 141 ms
4,376 KB |
testcase_08 | AC | 653 ms
4,992 KB |
testcase_09 | AC | 247 ms
4,376 KB |
testcase_10 | AC | 664 ms
4,968 KB |
testcase_11 | AC | 911 ms
5,412 KB |
testcase_12 | AC | 802 ms
5,180 KB |
testcase_13 | AC | 1,330 ms
6,724 KB |
testcase_14 | AC | 1,327 ms
6,700 KB |
testcase_15 | AC | 1,328 ms
6,704 KB |
testcase_16 | AC | 1,330 ms
6,636 KB |
testcase_17 | AC | 1,328 ms
6,588 KB |
testcase_18 | AC | 1,311 ms
6,592 KB |
testcase_19 | AC | 129 ms
6,596 KB |
testcase_20 | AC | 2 ms
4,380 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; constexpr int mod = 7,mod2 = 1000000007; vector<vector<long long>> Mul(vector<vector<long long>> A,vector<vector<long long>> B) { vector<vector<long long>>ans(A.size(),vector<long long>(A.size())); for(int i = 0; i < A.size(); i++) { for(int j = 0; j < A.size(); j++) { for(int k = 0; k < A.size(); k++) { ans[i][j] += A[i][k]*B[k][j]%mod; if(ans[i][j] >= mod) ans[i][j] -= mod; } } } return ans; } vector<vector<long long>> Pow(vector<vector<long long>> A,long long B) { vector<vector<long long>>ans(A.size(),vector<long long>(A.size())); ans[1][1] = 1; while (B) { if(1 & B) { ans = Mul(ans,A); } A = Mul(A,A); B /= 2; } return ans; } long long modpow(long long a,long long b) { long long ans = 1; while(b) { if(b & 1) { (ans *= a) %= mod; } (a *= a) %= mod; b /= 2; } return ans; } int dp[100100][7]; int main() { int K; cin >> K; dp[0][0] = 1; vector<int>D(K),L(K); for(int i = 0; i < K; i++) { cin >> D[i] >> L[i]; int c = modpow(10,L[i]); vector<vector<long long>>tmp(2,vector<long long>(2)); tmp[0][0] = 1; tmp[1][0] = 1; tmp[1][1] = 10; tmp = Pow(tmp,L[i]); int d = D[i]*(tmp[1][0])%mod; for(int j = 0; j < 7; j++) { dp[i+1][j] += dp[i][j]; if(dp[i+1][j] >= mod2) dp[i+1][j] -= mod2; int nxt = j*c+d; nxt %= mod; dp[i+1][nxt] += dp[i][j]; if(dp[i+1][nxt] >= mod2) dp[i+1][nxt] -= mod2; } } int ans = 0; for(int i = 1; i < 7; i++) { ans += 1ll*i*dp[K][i]%mod2; if(ans >= mod2) ans -= mod2; } cout << ans << endl; }