4337. [国家集训队 2026]字符串问题

【题目描述】

给定长度为 $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$ 取模后的结果。

【样例输入】

8
babaaabb
0 1 1 0 0 0 0 0

【样例输出】

0 0 0 1 1 2 0 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$。

特殊性质 A：对于所有 $1 \le i \le n$，均有 $f_i = [2 \mid i]$。  

特殊性质 B：存在正整数 $k$ 满足对于所有 $1 \le i \le n$，均有 $f_i = [k \mid i]$。

【来源】

IOI2026中国国家集训队集中培训 Day1 Task2