結果
問題 | No.1086 桁和の桁和2 |
ユーザー |
![]() |
提出日時 | 2020-06-19 23:50:42 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 42 ms / 3,000 ms |
コード長 | 1,692 bytes |
コンパイル時間 | 1,903 ms |
コンパイル使用メモリ | 170,772 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-07-22 17:55:53 |
合計ジャッジ時間 | 4,191 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 31 |
ソースコード
#include <bits/stdc++.h>int ri() {int n;scanf("%d", &n);return n;}struct FastIO {char buf[1000000];char *ptr = buf;void read() {int size;size = fread(buf, 1, sizeof(buf) - 1, stdin);buf[size] = '\0';ptr = buf;}FastIO () {read();}void inc() {if (++ptr == buf + sizeof(buf) || !*ptr) read();}template<typename Integer> Integer read() {bool neg = false;Integer res = 0;while ((*ptr < '0' || *ptr > '9') && *ptr != '-') inc();if (*ptr == '-') neg = true, inc();while (*ptr >= '0' && *ptr <= '9') res = res * 10 + *ptr - '0', inc();return neg ? -res : res;}} fastio;#define ri fastio.read<int>#define rs64 fastio.read<int64_t>#define MOD 1000000007int mpow(int a, int64_t b) {b %= 1000000006;int res = 1;for (; b; b >>= 1) {if (b & 1) res = (int64_t) res * a % MOD;a = (int64_t) a * a % MOD;}return res;}int main() {int n = ri();int64_t l[n], r[n];int d[n];for (auto &i : l) i = rs64();for (auto &i : r) i = rs64();for (auto &i : d) i = ri();int head = 0;while (head < n && !d[head]) head++;int pow10[31] = { 10 };for (int i = 0; i < 30; i++) pow10[i + 1] = (int64_t) pow10[i] * pow10[i] % MOD;auto mpow10 = [&] (int64_t b) {b %= 1000000006;int res = 1;for (int i = 0; b; b >>= 1, i++) if (b & 1) res = (int64_t) res * pow10[i] % MOD;return res;};int res = 1;for (int i = head; i < n; i++) {if (!d[i]) res = 0;int diff = (d[i] - (i ? d[i - 1] : 0)) % 9;int times = (!diff && i != head) + (int64_t) (mpow10(r[i]) - mpow10(l[i])) * 111111112 % MOD;res = (int64_t) res * times % MOD;}if (res < 0) res += MOD;printf("%d\n", res);return 0;}