#P6938. 回文串
回文串
题目描述
若字符串 的每个字符都是 内的整数,并且 可以由两个非空回文串拼接得到,就称 是双回文串。
求长度不超过 的不同双回文串的个数。若同一个字符串可以在不同位置拆成两个回文串,仍只计一次。
输入格式
一行两个正整数 。
输出格式
一行一个非负整数,表示答案对 取模后的结果。
数据范围
,。原赛时间限制 秒,内存限制 MB。
原赛采用捆绑测试。
| 子任务 | 特殊限制 | 原赛分值 |
|---|---|---|
| 1 | , | 7 |
| 2 | 15 | |
| 3 | 23 | |
| 4 | 27 | |
| 5 | 无 | 28 |
若字符串 S 的每个字符都是 [1,C] 内的整数,并且 S 可以由两个非空回文串拼接得到,就称 S 是双回文串。
求长度不超过 N 的不同双回文串的个数。若同一个字符串可以在不同位置拆成两个回文串,仍只计一次。
一行两个正整数 N,C。
一行一个非负整数,表示答案对 109+7 取模后的结果。
1≤N≤109,2≤C≤109。原赛时间限制 2 秒,内存限制 512 MB。
原赛采用捆绑测试。
| 子任务 | 特殊限制 | 原赛分值 |
|---|---|---|
| 1 | N≤15,C=2 | 7 |
| 2 | N≤18 | 15 |
| 3 | N≤300 | 23 |
| 4 | N≤106 | 27 |
| 5 | 无 | 28 |