#2124. 重复

    ID: 2124 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTS赛事:contest302来源:qoj.ac数据:公开样例字符串数学

重复

重复

题目描述

第二试重复(repeat) IOI 2019 中国国家队选拔 重复(repeat) 【题目背景】 贾樟柯在《山河故人》里说,“生活就是重复”。在生活中,人们总是喜欢重复自己 做过的事情。语言就是一个很经典的例子。 比如,我们在表示疑问时,总不满足于使用一个问号“?”;使用一连串的问号 “????”总是显得比较有力。 在表示抱歉时,一句“对不起”总显得不够情愿;连着表示“对不起对不起”才足 够表达自己的真诚。 【题目描述】 A 国就是一个喜欢重复的国家。在这个国家中,一个基本句子可以用一个长度恰好 为m 的小写字母字符串表示。为了表达自己对重复的喜爱,A 国的人们总喜欢把自己 想要表达的句子重复无限多次。 有时,这样的重复是充满意义的。A 国的人们把一个字典序小于给定的字符串s, 且长度和s 相同的小写字母字符串称为一个有意义的语义片段。他们想知道,有多少 个不同的基本句子(即长度恰好为m 的小写字母字符串)在经过无限重复后,可以从 中找出至少一个有意义的语义片段? 【输入格式】 从文件repeat.in 中读入数据。 输入文件的第一行为一个正整数m,表示基本句子的长度;第二行为一个小写字母 字符串s,其含义详见题目描述。 【输出格式】 输出到文件repeat.out 中。 输出一行一个整数,为满足条件的基本句子的数量。为了避免答案过大,你只需要 输出将答案对998244353 取模后的结果。 【样例1 输入】 3 abc 【样例1 输出】 79 第6 页 共9 页 第二试重复(repeat) IOI 2019 中国国家队选拔 【样例2 输入】 5 zxcvb 【样例2 输出】 11881375 【测试数据约定】 设字符串s 的长度为n,则n 、m 的范围遵循如下表格: 测试点编号 其他限制 m n m ≤5 n ≤10 m < n 1 m ≤30 n ≤30 2 m = n m ≤50 n ≤30 m > n 3 m ≤100 n ≤100 m < n 4 m ≤200 n ≤200 5 m = n m ≤300 n ≤200 m > n 6 m ≤300 n ≤2000 m < n 7 m ≤1000 n ≤1000 8 m = n m ≤2000 n ≤200 m > n 9 m ≤2000 n ≤2000 m > n 10 对于100% 的数据,保证1 ≤n, m ≤2000。 第7 页 共9 页

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

3
abc
79

样例 2

5
zxcvb
11881375