杭电多校第一场 1004 Distinct Sub-palindromes 题解

题目大意

长度为n的字符串，这个字符串由小写字母构成，求所有长度为n的字符串中，子回文串数量最小的串的数量为多少。

解题思路

一开始还以为是$26^n$，结果我们一个队交快速幂wa了三次。。

（我就wa了一次。。

首先，当长度为一的时候，很显然答案是26，因为无论你用哪个字母，子回文串的数量都是1。

当长度为二的时候，可以理解为在长度为一的串中，在空隙中插入其他字母，发现，无论你插入哪个字母，串的子回文串的数量都会加一，所以答案为$26^2$。当长度为三的时候，可以得出同样的结果，答案为$26^3$。

当长度大于三的时候，可以发现，当原长度为三的串中各个元素都不相同的时候，在其空隙中插入与左右两边都不相同的第三个字母，这个时候，串的回文子串的数量是不会增加的，所以答案为$262524$。

完整代码

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

int main(){
    int n;
    scanf("%d", &n);
    while(n--){
        int t;
        cin >> t;
        if(t==1)
            cout << 26 << endl;
        else if(t == 2)
            cout << 676 << endl;
        else if(t==3)
            cout << 17576 << endl;
        else cout << 15600 << endl;
    }
    return 0;
}