Problem J. Iris’ Food

猫猫 Iris 又在玩oql的键盘了。
在T天的时间里，每一天 Iris 会在玩oql键盘的时候敲下若干个字符，而这些字符恰好全都是0~9这
10个阿拉伯数字。经过统计，数字 ii 有 aia_i 个。
oql 每天可能会给Iris 喂一定数量的猫粮。他决定, 在 ∑i=09ai\sum_{i=0}^{9} a_i 个数字里选择 mm 个，经过重新排列后
形成一个十进制下 mm 位、且不包含前导0的非负整数 xx，然后 oql 将在这天给 Iris 投喂 xx 克的猫粮。
然而，Iris 还是一只小猫，不宜食用太多的猫粮。因此oql想让这个数字尽可能小。请你帮助 Iris 计算
出她每天能得到多少猫粮。
由于答案可能很大，你只需要输出答案对109+710^9+7取模的结果。请注意，你需要输出的是最小答案模
109+710^9+7后的结果，而不是xmod  109+7x \mod 10^9+7的最小值。

Input

第一行一个正整数 TT (1≤T≤1041 \leq T \leq 10^4),表示天数。
第2~ (T+1T+1) 行, 每行11个由空格分隔的非负整数 m,a0,a1,…,a9m, a_0, a_1, \dots, a_9 (1≤m≤1091 \leq m \leq 10^9, 0≤ai≤1090 \leq a_i \leq 10^9),表
示第 ii 天的情况。
数据保证有解，即至少能形成一个 mm 位不包含前导0的非负整数。

Output

对于每一天, 输出一行一个整数, 表示Iris 这一天能得到的猫粮对109+710^9+7取模后的结果。

Example

standard input

1
2
3
4
3
3 1 0 0 0 3 0 0 0 0 0
1 2 0 0 0 0 0 0 0 0 0
4 0 1 1 1 3 0 0 0 0 0

standard output

1
2
3
404
0
1234

题意

0~9的数字有 aia_i 个, 组成一个 m 位的无前导零的十进制数, 问最小可以是
多少 (模 10^9 + 7)。
T ≤ 10^4, a_i, m ≤ 10^9.

思路

找到1~9中最小的ii,满足 ai≥1a_i \ge 1 的非零的数,将其放在第一个,剩下的数
从小到大排列。
特别的,若 m=1,a0≥1m = 1, a_0 \ge 1,答案为0。
对于每一段连续相同数字的权值,可以通过类似c×10k1−19×10k2c \times \frac{10^{k_1}-1}{9} \times 10^{k_2} 的形式用
快速幂求出。
时间复杂度 O(Tlog⁡m)O(T \log m),带一个10的常数。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 10, mod = 1e9 + 7;

ll T, m, a[10];

ll qpow(ll x, ll y) {
    ll ans = 1;
    while (y) {
        if (y & 1) {
            ans = (ans * x) % mod;
        }
        y = y >> 1;
        x = (x * x) % mod;
    }
    return ans;
}

int main () {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> T;
    while (T--) {
        cin >> m;
        ll ans = 0;
        for (int i = 0; i <= 9; ++i) {
            cin >> a[i];
        }
        if (m == 1 and a[0] >= 1) {
            cout << 0 << '\n';
            continue;
        }
        m--;
        for (int i = 1; i <= 9; ++i) {
            if (a[i] > 0) {
                a[i]--;
                ans += i * qpow(10, m) % mod;
                break;
            }
        }
        for (int i = 0; i <= 9; ++i) {
            if (a[i] > 0 and m > 0) {
                ll cnt = min(m, a[i]);
                ans += (qpow(10, cnt) - 1) * qpow(9, mod - 2) * i % mod * qpow(10, m - cnt);
                ans %= mod;
                m -= cnt;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

To be continued…?