結果
問題 | No.1086 桁和の桁和2 |
ユーザー |
![]() |
提出日時 | 2020-06-19 22:27:20 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,077 bytes |
コンパイル時間 | 512 ms |
コンパイル使用メモリ | 46,080 KB |
最終ジャッジ日時 | 2025-01-11 07:01:52 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 11 WA * 1 TLE * 19 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:57:15: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 57 | scanf ("%d", &N); | ~~~~~~^~~~~~~~~~ main.cpp:58:43: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 58 | for (int i = 0; i < N; i++) scanf ("%lld", &L[i]); | ~~~~~~^~~~~~~~~~~~~~~ main.cpp:59:43: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 59 | for (int i = 0; i < N; i++) scanf ("%lld", &R[i]); | ~~~~~~^~~~~~~~~~~~~~~ main.cpp:60:43: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 60 | 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 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; } }iden, all, base[70]; pair<matrix, matrix> fpow(int i, long long n) { if (n <= 0) return { iden, matrix() }; if (n == 1) return { base[i], iden }; auto half = fpow(i + 1, n / 2); half.second = half.second * (iden + base[i]); if (n % 2){ half.second = half.second + half.first; half.first = half.first * base[i]; } return half; } int main() { for (int i = 0; i < 9; i++){ iden.a[i][i] = 1; for (int j = 0; j < 9; j++) all.a[i][j] = 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 low = fpow(0, L[i]); auto upp = fpow(0, R[i] - L[i]); matrix p = all * low.first * upp.second; ans = ans * (p.a[0][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; }