1002. 表达式 2

题目描述

河灵上小学二年级了。最近，河灵在学校里学到了最新最酷的乘法运算。这一天，老师给河灵一个由 n 个非零数字构成的数字串 S。河灵可以在数字串的任意两个相邻数字之间的空隙中插入乘号，使其变成一个数字表达式。例如数字串 1234，河灵可以在第一个空隙和第三个空隙中插入乘号，就可以得到表达式 1 × 23 × 4。简单的表达式求值已经难不倒河灵了，该去研究更有意思的数学问题了！于是河灵交给了你这个问题。对于每一个整数 k (0 ≤ k < n)，你需要求出：在数字串 S 的 n − 1个空隙中插入恰好 k 个乘号，使其变成一个数学表达式，计算所有不同插入方案所得表达式的结果之和。答案对 998244353 取模。

输入格式

每个测试点中包含多组测试数据。输入的第一行包含一个正整数 T (

1 ≤ T ≤ 2 × 105 )，表示数据组数。对于每组测试数据：第一行一个正整数 n (1 ≤ n ≤ 105 )，表示数字串长度。第二行一个长度为 n 的数字串 S，保证 S 的每一位数字均为 1 ∼ 9 中的某一个。保证所有测试数据中 n 之和不超过 2 × 105。

输出格式

对于每组测试数据：输出一行 n 个整数 ans0, ans1, …, ansn−1，其

中 ansi 表示当 k = i 时问题的答案对 998244353 取模后的值。

样例输入

2
3
777
5
32768

样例输出

777 1078 343
32768 81324 67124 21144 2016

来源：官方题面 PDF（2026"钉耙编程"暑期联赛 第2场）