P14926 [北大集训 2025] 字符串问题

给定长度为 $n$ 的字符串 $s$ 和系数序列 $f_1, f_2, \dots, f_n$。 定义一个正整数 $d$ 是一个子串 $s[l,r]$ ($1 \le l \le r \le n$) 的**周期**，当且仅当 $d \le r-l+1$ 且对于任意 $l \le i \le r-d$，均有 $s_i = s_{i+d}$。 定义一个正整数 $d$ 是一个子串 $s[l,r]$ ($1 \le l \le r \le n$) 的**整周期**，当且仅当 $d$ 是 $s[l \dots r]$ 的周期，且 $d$ 整除 $r-l+1$。 对于 $1 \le l \le r \le n$，定义子串 $s[l,r]$ 的**价值**为 $w(l,r) = f_{(r-l+1)/d}$，其中 $d$ 是子串 $s[l,r]$ 的**最小整周期**。 对于所有 $1 \le i \le n$，求所有以 $i$ 为右端点的子串的价值之和，即 $\sum_{j=1}^{i} w(j,i)$。由于答案可能较大，你只需要求出答案对 $998,244,353$ 取模后的结果。

从标准输入读入数据。 输入的第一行包含一个正整数 $n$，表示字符串 $s$ 的长度。 输入的第二行包含一个长度为 $n$ 的字符串 $s$。 输入的第三行包含 $n$ 个非负整数 $f_1, f_2, \dots, f_n$，表示给定的系数序列。

输出到标准输出。 输出一行 $n$ 个非负整数，其中第 $i$ ($1 \le i \le n$) 个非负整数表示所有以 $i$ 为右端点的子串的价值之和对 $998,244,353$ 取模后的结果。

### 【样例 1 解释】 以下为所有价值非 $0$ 的子串： - 子串 $s[1,4] = \text{baba}$ 的最小整周期为 $2$，价值为 $1$。 - 子串 $s[4,5] = \text{aa}$ 的最小整周期为 $1$，价值为 $1$。 - 子串 $s[4,6] = \text{aaa}$ 的最小整周期为 $1$，价值为 $1$。 - 子串 $s[5,6] = \text{aa}$ 的最小整周期为 $1$，价值为 $1$。 - 子串 $s[7,8] = \text{bb}$ 的最小整周期为 $1$，价值为 $1$。 ### 【子任务】 对于所有测试数据，均有： - $1 \le n \le 10^6$； - 对于所有 $1 \le i \le n$，$s_i$ 均为小写英文字母； - 对于所有 $1 \le i \le n$，均有 $0 \le f_i \le 10^9$。 | 子任务编号 | 分值 | $n \le$ | 特殊性质 | |:-:|:-:|:-:|:-:| | 1 | 10 | $100$ | 无 | | 2 | 15 | $5 \times 10^3$ | 无 | | 3 | 25 | $2 \times 10^5$ | A | | 4 | 10 | $2 \times 10^5$ | B | | 5 | 20 | $10^6$ | 无 | | 6 | 20 | $10^6$ | 无 | 特殊性质 A：对于所有 $1 \le i \le n$，均有 $f_i = [2 \mid i]$。 特殊性质 B：存在正整数 $k$ 满足对于所有 $1 \le i \le n$，均有 $f_i = [k \mid i]$。