結果
問題 | No.1086 桁和の桁和2 |
ユーザー |
![]() |
提出日時 | 2020-06-19 22:41:44 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,579 bytes |
コンパイル時間 | 681 ms |
コンパイル使用メモリ | 45,568 KB |
最終ジャッジ日時 | 2025-01-11 07:16:53 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 11 WA * 8 TLE * 12 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:85:15: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 85 | scanf ("%d", &N); | ~~~~~~^~~~~~~~~~ main.cpp:86:43: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 86 | for (int i = 0; i < N; i++) scanf ("%lld", &L[i]); | ~~~~~~^~~~~~~~~~~~~~~ main.cpp:87:43: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 87 | for (int i = 0; i < N; i++) scanf ("%lld", &R[i]); | ~~~~~~^~~~~~~~~~~~~~~ main.cpp:88:43: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 88 | for (int i = 0; i < N; i++) scanf ("%d", &D[i]); | ~~~~~~^~~~~~~~~~~~~
ソースコード
#include <stdio.h> #include <algorithm> using namespace std; int N, D[100100]; long long L[100100], R[100100]; const long long mod = 1000000007; struct arr{ arr(){ for (int i = 0; i < 9; i++) a[i] = 0; } long long a[9]; arr operator +(arr t){ arr r; for (int i = 0; i < 9; i++){ r.a[i] = (a[i] + t.a[i]) % mod; } return r; } }; struct matrix{ matrix(){ for (int i = 0; i < 9; i++) for (int j = 0; j < 9; j++) a[i][j] = 0; } long long a[9][9]; matrix operator +(matrix t){ matrix r; for (int i = 0; i < 9; i++) for (int j = 0; j < 9; j++){ r.a[i][j] = (a[i][j] + t.a[i][j]) % mod; } return r; } matrix operator *(matrix t){ matrix r; for (int i = 0; i < 9; i++) for (int j = 0; j < 9; j++){ r.a[i][j] = 0; for (int k = 0; k < 9; k++){ r.a[i][j] = (r.a[i][j] + a[i][k] * t.a[k][j]) % mod; } } return r; } arr operator *(arr t){ arr r; for (int i = 0; i < 9; i++) for (int j = 0; j < 9; j++){ r.a[i] = (r.a[i] + a[i][j] * t.a[j]) % mod; } return r; } }iden, base[70]; arr sum(matrix t) { arr r; for (int i = 0; i < 9; i++) for (int j = 0; j < 9; j++){ r.a[i] = (r.a[i] + t.a[i][j]) % mod; } return r; } pair<arr, arr> fpow(int i, long long n) { if (n <= 0) return { sum(iden), arr() }; if (n == 1) return { sum(base[i]), sum(iden) }; auto half = fpow(i + 1, n / 2); half.second = (iden + base[i]) * half.second; if (n % 2){ half.second = half.second + half.first; half.first = base[i] * half.first; } return half; } int main() { for (int i = 0; i < 9; i++) iden.a[i][i] = 1; for (int i = 0; i < 9; i++) for (int j = 0; j < 10; j++) base[0].a[i][(i + j) % 9]++; for (int i = 1; i < 70; i++) base[i] = base[i - 1] * base[i - 1]; scanf ("%d", &N); for (int i = 0; i < N; i++) scanf ("%lld", &L[i]); for (int i = 0; i < N; i++) scanf ("%lld", &R[i]); for (int i = 0; i < N; i++) scanf ("%d", &D[i]); int s = 0; while (s < N && D[s] == 0) s++; for (int i = s; i < N; i++) if (D[i] == 0){ puts("0"); return 0; } for (int i = s; i < N; i++){ L[i - s] = L[i]; R[i - s] = R[i]; D[i - s] = D[i]; } N -= s; long long ans = 1; int ld = 0; for (int i = 0; i < N; i++){ int nd = (D[i] + 9 - ld) % 9; auto upp = fpow(0, R[i] - L[i]); arr p = upp.second; long long low = L[i]; for (int b = 0; low; b++){ if (low & 1) p = base[b] * p; low /= 2; } ans = ans * (p.a[nd] + (nd == 0)) % mod; ld = nd; } bool g = N > 0; for (int i = 0; i < N; i++) if (D[i] != 9) g = 0; if (g) ans = (ans + mod - 1) % mod; printf ("%lld\n", ans); return 0; }