#P17730. [2026年福建省队集训]once again
[2026年福建省队集训]once again
题目背景
小青蛙在备课。
小青蛙看到一个题,很快想出来一个多项式做法。
小青蛙看题解,题解说有一个平方做法,但是小青蛙没看懂。
小青蛙又想了一会,虵觉得这题肯定能几乎线性。
但是小青蛙懒得继续想,于是虵把这个题丢给了 GPT-5.5 Thinking (xhigh)。过了 4 分钟 44 秒,GPT 大人果然给了一个符合小青蛙想象的做法。
然后小青蛙很快发现其实还能再加十个零。于是虵把加了二十个零的原题出给了你。
题目描述
给定一个正整数 和一个 01 串 。
对于一个长为 的 01 串 ,如果存在 的某个循环移位,使得 是这个循环移位后的串的子串,那么称 是好的。
换句话说,把 看成一个环,如果能在这个环上从某个位置开始连续读出 ,那么 是好的。
请你求有多少个长为 的 01 串是好的。答案对 取模。
注意,两个 01 串只要作为普通字符串不同,就认为它们不同。即使它们互为循环移位,也会被分别计数。
输入格式
第一行包含一个正整数 。
第二行包含一个 01 串 。
输出格式
输出一个整数,表示好的长为 的 01 串数量对 取模后的结果。
输入输出样例 #1
输入 #1
2
0
输出 #1
3
输入输出样例 #2
输入 #2
4
1010
输出 #2
2
输入输出样例 #3
输入 #3
20
10101010101010
输出 #3
962
说明/提示
样例 #1 中,好的字符串为 00,01,10,共 个。
样例 #2 中,好的字符串为 1010,0101,共 个。
对于 的数据,;
对于 的数据,;
对于 的数据,;
对于 的数据,;
对于 的数据,,, 仅包含字符 0 和 1。