問題一覧 > 通常問題

No.1086 桁和の桁和2

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 66
作問者 : tyawanmusityawanmusi / テスター : QCFiumQCFium
4 ProblemId : 3825 / 出題時の順位表
問題文最終更新日: 2020-06-19 17:40:04

問題文

関数$f(X)$を次のように定義します。
$f(X) = \left\{ \begin{array}{ll} X & (X < 10) \\ f(Xの桁和) & (10 \le X)\end{array} \right.$
次の条件を満たす要素数$N$の整数列$A$を「美しい数列」と定義します。

  • 全ての$i(1 \le i \le N)$について、$10^{L_i} \le A_i < 10^{R_i}$ または $A_i = 0$
  • 全ての$i(1 \le i \le N)$について、$f(f(A_1) + f(A_2) + \dots + f(A_i)) = D_i$
整数$N$、整数列$L, R, D$が与えられます。
「美しい数列」の総数を$10^9+7$で割ったあまりを求めてください。

制約

  • $1 \le N \le 10^5$
  • $0 \le L_i < R_i \le 10^{18}$
  • $0 \le D_i \le 9$
  • $N, L_i, R_i, D_i$は整数

入力

$N$
$L_1 \ L_2 \dots L_N$
$R_1 \ R_2 \dots R_N$
$D_1 \ D_2 \dots D_N$

1行目には整数$N$が入力されます。
2行目には整数列$L$が空白区切りで入力されます。
3行目には整数列$R$が空白区切りで入力されます。
4行目には整数列$D$が空白区切りで入力されます。

出力

「美しい数列」の総数を$10^9+7$で割ったあまりを出力してください。
最後に改行してください。

サンプル

サンプル1
入力
2
0 1
1 2
3 4
出力
10

「美しい数列」の例として、$(3,10),(3,55)$などが挙げられます。

この入力は、

  • $1 \le A_1 < 10$または$A_1 = 0$
  • $10 \le A_2 < 100$または$A_2 = 0$
  • $f(f(A_1))=3$
  • $f(f(A_1)+f(A_2))=4$
であることを意味します。

サンプル2
入力
5
8 13 21 34 55
89 144 233 377 610
1 1 2 3 5
出力
880448910

「美しい数列」の総数を$10^9+7$で割ったあまりを求めてください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。