#P9772. [2020年省队模拟]双回文

    ID: 6401 传统题 2000ms 512MiB 尝试: 2 已通过: 2 难度: 8 上传者: 标签>CF2500提高+/省选-对称性分析字符串周期乘法原理递推计数倍数枚举贡献法

[2020年省队模拟]双回文

题目描述

正读和反读相同的字符串叫作回文串。如果一个非空字符串本身是回文串,或者可以由两个非空回文串拼接而成,就称它为双回文串。

求使用前 kk 个小写英文字母、长度不超过 nn 的不同双回文串的个数。一个字符串即使有多种拆分方法,也只计一次。答案对 998244353998244353 取模。

输入格式

一行两个整数 n,kn,k。

输出格式

输出一行一个整数,表示答案对 998244353998244353 取模后的结果。

样例

3 3
33
6 2
114

数据范围

1≤n≤1051\le n\le10^5,1≤k≤261\le k\le26。对于原赛 1010 分的数据,n≤5n\le5。对于原赛 2020 分的数据,n≤1000n\le1000。

原 PDF 题面