Distinct Sub-palindromes（HDU-6754）

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), ui≠vi. 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≤105), denoting the number of test cases.

The only line of each test case contains an integer n (1≤n≤109).

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的字符串，要求子回文串尽可能的少。

思路：
这道题的话，给的题面感觉不好理解，读了好多遍题才读懂，看来阅读要下点功夫了。。。然后跟队友讨论发现就是能组成最少不同子回文串的最少不同字符串数量是n个26相乘。但是后来又发现当n>=4的时候，最少的子回文串就是3个，因为我们只需要3个不同的字母无限填充即可，所以当n>=4的时候就是262524。

AC代码：

#include <bits/stdc++.h>
typedef long long ll;
const int maxx=100010;
const int inf=0x3f3f3f3f;
const int mod=1000000009;
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        if(n==1)
        cout<<26<<endl;
        else if(n==2)
        cout<<26*26<<endl;
        else if(n==3)
        cout<<26*26*26<<endl;
        else
        cout<<26*25*24<<endl;
    }
    return 0;
}

赏

×

纯属好玩

扫码打赏，你说多少就多少

打开支付宝扫一扫，即可进行扫码打赏哦