[杭电多校2020]第一场 1004 Distinct Sub-palindromes

Distinct Sub-palindromes

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6754

1004.Distinct Sub-palindromes
Time Limit: 5000/2500 MS (Java/Others)
Memory Limit: 524288/524288 K (Java/Others)

Problem Description
S is a string of length n. S consists of lowercase English alphabets.
Your task is to count the number of different S with the minimum number of distinct sub-palindromes. Sub-palindrome is a palindromic substring.
Two sub-palindromes u and v are distinct if their lengths are different or for some i (0 ≤ i ≤ length), u_i≠ v_i. For example, string “aaaa” contains only 4 distinct sub-palindromes which are “a”, “aa”, “aaa” and “aaaa”.
Input
The first line contains an integer T (1 ≤ T ≤ 10⁵), denoting the number of test cases.
The only line of each test case contains an integer n (1 ≤ n ≤ 10⁹).
Output
For each test case, output a single line containing the number of different strings with minimum number of distinct sub-palindromes.
Since the answer can be huge, output it modulo 998244353.
Sample Input
2
1
2
Sample Output
26
676

题面

思路

给的题解为：

题意：要求给一个n，从26个小写字母里选，构造一个长度为n的字符串，使得字符串的子串为回文串的数量最少，问这样的字符串有多少个。

首先可以看出回文子串个数至少为所用字母种类的数量。

当n=1时:

每种情况的回文子串都是自己，都只有1个回文子串，故有26种情况。

当n=2时：

这时可以找出有aa,ab这两种类型。这两种类型的回文子串都是2个，所以最少的情况就是2个回文子串，所以这两种类型都可以，故有26*26=676种情况。

当n=3时：

这时可以找出有aaa,aab（abb）,aba（bab）,abc（acb，bac，bca，cab，cba）这样的四种情况，这四种的回文子串都有3个。所以这四种类型都可以，故有262626=17576种情况。

当n>3时：

当n=4时，我们考虑在n=3的四种情况上添加一个字母，那么回文子串的个数肯定>=3，如果在类型1，2 ，3中加一个新的字母必然会增加回文子串的个数，而如果是在类型1里面再加一个a变成aaaa的话，就会增加一个回文子串，在第二种类型中添加一个a或者b变成aaba或者aabb都会增加一个回文，第三种也是一样的，只有在第四种中，如果在后面添加一个a的话，变成abca那么它的回文子串是不增加的。所以选择abca这种类型。
再继续增加下去，会发现如果是abcabcabc……这样循环下去的话，这样能保证s内没有长度大于1的回文子串，且长度为1的不同的回文子串的个数总是3个，也就是最小的情况。
故n>3时，回文子串的个数最少为3，形式为abcabcabc……,所以有262524=15600种情况。

那么代码就直接根据情况输出即可：

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int ncase;
	for (cin >> ncase; ncase--; ) {
		int n; cin >> n;
		cout << (vector<int>){1, 26, 676, 17576, 15600}[min(n, 4)] << "\n";
	}
	return 0;
}