#P15893. [Roi2023 Regional]普通字符串题

[Roi2023 Regional]普通字符串题

题目描述

称两个字符串 ss 和 tt 等价,如果对于任意长度为 22 的字符串 uu,uu 在 ss 中的出现次数等于 uu 在 tt 中的出现次数。

例如,字符串 aaaba、abaaa 和 baaab 两两等价:

  • aa 出现 22 次;
  • ab 出现 11 次;
  • ba 出现 11 次;
  • bb 出现 00 次。

而字符串 abb 和 bba 不等价。

现在给定 QQ 个只由字符 a、b、c 组成的字符串。对每个字符串,求与它等价的非空字符串数量,要求这些字符串也只由 a、b、c 组成。由于答案可能很大,请输出对 109+710^9+7 取模后的结果。

输入格式

第一行包含一个整数 GG,表示当前测试所属的子任务编号。样例中 G=0G=0。

第二行包含一个整数 qq(1≤q≤1051\le q\le 10^5)。接下来给出 qq 个字符串,每个字符串仅由 a、b、c 组成。

所有字符串的总长度不超过 10610^6。

输出格式

输出 qq 个整数,每个整数对应一个输入字符串的答案。通常每行输出一个答案。

子任务

设 nin_i 为第 ii 个字符串的长度,LL 为所有输入字符串长度之和,ww 为所有询问中未取模的最大答案。

子任务 分值 附加限制 依赖
1 11 字符串不含 c -
2 13 字符 a 与 c 在字符串中不相邻 1
3 11 ni≤13n_i\le 13 -
4 10 L≤40L\le 40 3
5 9 L≤60L\le 60 3,4
6 13 w≤100w\le 100,L≤105L\le 10^5 -
7 33 无 1--6

样例

0
4
abaa
abca
ccbca
bacc
3
3
2
1

样例解释

  • 与 abaa 等价的字符串有:abaa、aaba、baab;
  • 与 abca 等价的字符串有:abca、bcab、cabc;
  • 与 ccbca 等价的字符串有:ccbca、cbcca;
  • 与 bacc 等价的字符串只有:bacc。