2020杭电多校第一场 1004 Distinct Sub-palindromes（思维/构造）

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<=3时直接输出pow(26, n)，当n大于3时构造abcabcabc……这样能保证s内没有长度大于1的回文子串，且长度为1的不同的回文子串只有三个（如果用ababab这样构造显然会有aba这样的子串，不满足不同的回文子串最小；如果用四个不同字母来构造又浪费了…）。当然a，b和c可以换成任意三个字母，因此直接输出C(26, 3) * A(3, 3)即可。

#include <bits/stdc++.h>
#define mod 998244353
using namespace std;
long long fpow(long long a, long long b)
{
    long long ans = 1 % mod;
    for(; b; b >>= 1)
    {
        if(b & 1) ans = ans * a % mod;
        a = a * a % mod;
    }
    return ans;
}
int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        long long n;
        cin >> n;
        if(n <= 3) cout << fpow(26, n) << endl;
        else cout << 26 * 25 * 24 / 6 * 6 << endl;
    }
    return 0;
}