結果
問題 | No.1086 桁和の桁和2 |
ユーザー |
|
提出日時 | 2020-06-19 22:30:42 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,639 ms / 3,000 ms |
コード長 | 1,631 bytes |
コンパイル時間 | 2,632 ms |
コンパイル使用メモリ | 201,884 KB |
最終ジャッジ日時 | 2025-01-11 07:05:04 |
ジャッジサーバーID (参考情報) |
judge1 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 31 |
ソースコード
#include <bits/stdc++.h>using namespace std;constexpr int mod = 1000000007;long long repeat(long long l) {vector<vector<long long>> x = {{10, 0}, {1, 1}};vector<long long> v = {1, 0};auto sq = [&](auto &x) {auto y = x;for (int i = 0; i < 2; i++) {for (int j = 0; j < 2; j++) {y[i][j] = 0;for (int k = 0; k < 2; k++) {y[i][j] += x[i][k] * x[k][j] % mod;}y[i][j] %= mod;}}return y;};auto mul = [&](auto &x, auto &v) {auto ret = v;for (int i = 0; i < 2; i++) {ret[i] = 0;for (int j = 0; j < 2; j++) {ret[i] += x[i][j] * v[j] % mod;}ret[i] %= mod;}return ret;};while (l) {if (l & 1) v = mul(x, v);x = sq(x);l >>= 1;}return v[1];}int main() {cin.tie(nullptr);ios::sync_with_stdio(false);int N; cin >> N;vector<long long> L(N), R(N), D(N);for (auto &x: L) cin >> x;for (auto &x: R) cin >> x;for (auto &x: D) cin >> x;int Dc = 0;long long Ans = 1;for (int i = 0; i < N && Ans; i++) {if (D[i] == 0) {if (Dc != 0) Ans = 0;continue;}int Diff = (D[i] - Dc + 9) % 9;long long U = repeat(R[i]) - repeat(L[i]);U = (U % mod + mod) % mod;if (Diff == 0 && Dc != 0) U++;Dc = D[i];Ans = Ans * U % mod;}cout << Ans << "\n";return 0;}