#P18530. Counter Reset Problem
Counter Reset Problem
Counter Reset Problem
机械计数器是一种常见的辅助工具。经典计数器通常有显示当前计数的区域、计数按钮和归零按钮。传统的 位十进制机械计数器通过内部复杂的机械结构,使每次按下计数按钮都恰好将原计数在模 意义下加 ;转动侧面的归零旋钮,则会带动某些数位转动一格。转动足够多次后,可以把任意初始状态恢复为全零。
计数器内部触点可能接触不良,影响转动归零旋钮时数位变化的具体方式。本题假设计数器每转动一次归零旋钮,都按以下规则改变计数。始终保留全部 位,包括前导零,数位从最高位起编号为 :
- 最高位总是转动一格,即该数位在模 意义下加 。
- 对第 位(),如果最高位和第 位都等于 ,且第 位至第 位的数位均不大于 ,则第 位与最高位一起转动一格,也在模 意义下加 。当 时,中间没有数位,此条件自然满足。
- 不满足上述条件的其他数位保持不变。
一次旋转中,各数位是否转动均按本次旋转前的状态判断,并同时变化。例如,1151 转动一次后变成 2251;9791 转动一次后变成 0701。
对一个整数 (可能带前导零),将计数器从 转到全零状态所需的最少旋转次数,称为 的清零旋转次数。初始状态已经全零时,该次数为 。
对于一个 位十进制机械计数器,请计算闭区间 中所有整数的清零旋转次数之和。
输入格式
第一行包含一个整数 ,。
第二行包含两个整数 ,二者都恰好包含 个十进制数位,可能带前导零。保证 。
输入只有一组数据。
输出格式
输出一行一个非负整数,表示所求总和对 取模后的结果。
样例 1
输入:
2
19 23
输出:
51
样例 2
输入:
6
100084 518118
输出:
9159739
样例 3
输入:
12
040139021316 234700825190
输出:
771011551
以上是三个分别独立的样例,不是同一份输入中的多组数据。