#P8726. [2024年山东第三轮集训]数

[2024年山东第三轮集训]数

数

题目描述

小 a 有一些十进制数码,其中数字 ii 有 aia_i 个,0≤i≤90\le i\le9。用全部数码拼成两个正整数 A,BA,B,每个数码恰好使用一次。两个数均不能有前导零,也不能为零。

求 ∣A−B∣|A-B| 的最小值。如果无法拼成两个满足要求的正整数,输出 -1。

输入格式

第一行一个整数 TT。接下来 TT 行,每行十个整数,依次为 a0,…,a9a_0,\ldots,a_9。

输出格式

每组输出一行。无解输出 -1;否则输出最小差值对 998244353998244353 取模的结果。先最小化实际差值,再取模。

样例

4
0 1 1 1 1 0 0 0 0 0
2 2 0 0 0 0 0 0 0 0
3 0 0 0 0 0 0 1 1 0
1 0 0 0 0 0 0 0 1 2
7
0
620
1

数据范围

1≤T≤1001\le T\le100,0≤ai≤1090\le a_i\le10^9。

子任务 分值 附加限制
1 20 ∑ai≤8\sum a_i\le8
2 ∑ai≤36\sum a_i\le36
3 所有 ai≤100a_i\le100
4 所有 ai≤105a_i\le10^5
5 无