题目链接

题意：
给出一个长度为 n 的序列 ai ，定义该序列的回文度为区间 ( l , r ) 的对数，其中 l , r 需要满足1 ≤ l ≤ r ≤ n 且对 al , … , ar重排之后，长度为n的序列（原序列）变成回文序列。

题解：
统计每个数字出现的次数num[i]，如果序列长度为偶数且num[i]中有奇数或者序列长度为奇数且num[i]中有超过一个奇数则不可能形成回文，方案数为0。
实际上只要有大于一个奇数就不成立（以上两种情况可以统一为这一种情况）。

否则首先从两端开始往中间找已经回文的最长长度pos，然后分别考虑两个端点还可以往中间走多远，假设左边还可以走len1，右边还可以走len2。
那么
（1）左端的 1 ---- pos + len1 + 1 与 右端的 pos + 1 均可以形成一对 （ l ，r ）
（2）左端的 pos + 1 与 右端的 n - pos - len2 ---- n 均可以形成一对（ l ， r ）

重复算了一部分 左端 pos + 1 与 右端 pos + 1
实际上最终答案应该是（ pos + len1 + 1 ）* （pos + 1 ） + （pos + 1） * len2
其中（pos + 1） *len2 对应第二种情况，并且去掉了重复的部分。

最终答案为（pos + 1） * （pos + 1 + len1 + len2）

现在考虑 len1 len2怎么求。
以左边往右走为例，从pos+1开始走，
只需统计已经使用的数字个数，只要其不超过该数字个数的一半就可以继续走。

若当前已使用的数字的个数，已经超过了该数字的一半，
（1）若当前位置在回文中心的左侧，则当前位置不符合要求。
（2）若当前位置是回文中心（数列有奇数个的情况）且当前数字就是那个有奇数个的数字，则当前位置符合要求，继续走；否则，当前位置不符合要求。
（3）若当前位置在回文中心的右侧，但是其对称位置的数字与当前数字相等，则当前位置符合要求，继续走；否则当前位置不符合要求。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<set>
#define ll long long
#define pr make_pair
#define pb push_back
#define ui unsigned int
#define lc (cnt<<1)
#define rc (cnt<<1|1)
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const int mod=1000000007;
const double eps=1e-8;
const double pi=acos(-1.0);
const int maxn=200100;
const int maxm=100100;
const int up=100000;

int a[maxn],b[maxn],c[maxn];

int main(void)
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        b[a[i]]++;
    }

    //判断能不能形成回文
    int cnt=0;
    for(int i=1;i<=n;i++)
        cnt+=(b[i]&1);
    if(cnt>1)
    {
        printf("0\n");
        return 0;
    }

    //找到左右回文最大长度
    int pos=-1;
    for(int i=1;i<=n;i++)
    {
        if(a[i]!=a[n-i+1])
        {
            pos=i-1;
            break;
        }
        else b[a[i]]-=2;
    }
    //本身就是个回文
    if(pos==-1)
    {
        printf("%lld\n",1ll*n*(n+1)/2);
        return 0;
    }

    int len=0;
    for(int i=pos+1;i<=n;i++)
    {
        c[a[i]]++;
        if(c[a[i]]*2>b[a[i]])
            if(i<n-i+1||i==n-i+1&&b[a[i]]%2==0||a[i]!=a[n-i+1]) break;
        len++;
    }
    memset(c,0,sizeof(c));
    for(int i=n-pos;i>=1;i--)
    {
        c[a[i]]++;
        if(c[a[i]]*2>b[a[i]])
            if(i>n-i+1||i==n-i+1&&b[a[i]]%2==0||a[i]!=a[n-i+1]) break;
        len++;
    }
    printf("%lld\n",1ll*(pos+1)*(pos+1+len));
    return 0;
}