5481: Separated Number
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：2
解决：1
题目描述
Cathy loves numbers, and recently she fell in love with the separation of numbers.
A separation of a number is defined as dividing the number into contiguous parts. For example, we can call (11)(451)(4) a separation of the number 114514. The value of one separation is the sum of all the separated parts(the value of (11)(451)(4) equals to 11+451+4=466). If one part has leading zeros, it is also valid, so the separation (1)(00) of number 100 is a valid separation too. Now Cathy has a number x without leading zeros, and she wants to know the total value of separations which divide the number into no more than k parts. She is not quite smart so she asked you for help.
Since the answer may be very large, you only need to output the answer modulo 998244353.
A separation of a number is defined as dividing the number into contiguous parts. For example, we can call (11)(451)(4) a separation of the number 114514. The value of one separation is the sum of all the separated parts(the value of (11)(451)(4) equals to 11+451+4=466). If one part has leading zeros, it is also valid, so the separation (1)(00) of number 100 is a valid separation too. Now Cathy has a number x without leading zeros, and she wants to know the total value of separations which divide the number into no more than k parts. She is not quite smart so she asked you for help.
Since the answer may be very large, you only need to output the answer modulo 998244353.
输入
The first line contains a number T(1≤T≤5), the number of testcases.
For each testcase, there are two lines.
The first line contains a number k, the maximum number of parts.
The second line contains a number x, the queried number.
Let n be the number of digits of x, and we will have 1≤n≤10^6 and 1≤k≤n.
It is guaranteed that for all testcases, ∑n≤10^6.
For each testcase, there are two lines.
The first line contains a number k, the maximum number of parts.
The second line contains a number x, the queried number.
Let n be the number of digits of x, and we will have 1≤n≤10^6 and 1≤k≤n.
It is guaranteed that for all testcases, ∑n≤10^6.
输出
For each testcase, output one number in one line, the answer modulo 998244353.
样例输入 复制
1
3
100样例输出 复制
112提示
In the sample, there are 4 possible separations with no more than 3 parts, (100),(1)(00),(10)(0),(1)(0)(0), and their values are 100, 1+0=1, 10+0=10, 1+0+0=1 respectively, so the answer will be 100+1+10+1=112.