牛客周赛59F
注意是所有子序列的回文值。

贡献法的思路。贡献肯定来自两个不同的元素。那对于两个不同的元素$a_i,a_j$，他们的贡献即可能存在多少个子序列里，使得它们要进入这个子序列的计算。因此下标$i、j$一定对称。
在位置i和j中间，选任意数量的数，都能满足i和j对称。在位置i左边和j右边，则必须选同样数量的数才能使得i和j对称。说白了i,j之间选多少个数没关系，也就是只需要外部选择同样数量的数就能使得i和j对称。

那么假设i的左边有x个元素，j的右边有y个元素，i和j中间有z个元素，则$a_i,a_j$的贡献为：
$$ 2^n*(1+C_x^1*C_y^1+C_x^2*C_y^2+…)=2^n*\sum_{k=0}^{min(x,y)} C_x^k*C_y^k $$
因此最后的答案为：
$$ \sum_{1<=i<j<=n \ \ a_i\neq a_j} 2^{j-i+1}*\sum_{k=0}^{min(left,right)}C_{left}^k*C_{right}^k $$

时间复杂度：找到两个不同的端点n方，算组合数n，最后n^3。

范德蒙德卷积

推论4：$\sum_{i=0}^m C_{n}^iC_m^i = C_{n+m}^m$ 优化到只需要算一次组合数，n^2枚举就可以了

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

using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;

const ll mod = 1e9+7;
ll n;
ll fac[4010],ifac[4010];
ll a[2010];
ll qmi(ll a,ll b,ll mod){
    ll res=1;
    while(b){
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
void init(){
    fac[0] = ifac[0] = 1;
    for(int i=1;i<4010;i++){
        fac[i] = fac[i-1]*i%mod;
        ifac[i] = ifac[i-1]*qmi(i,mod-2,mod)%mod;
    }
}
ll C(int n,int m){
    if(n<m) return 0;
    return fac[n]*ifac[n-m]%mod *ifac[m]%mod;
}
int main(){

    init();
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    ll ans = 0;
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++){
            if(a[i]!=a[j]) 
                ans=(ans+qmi(2,j-i-1,mod)*C(i-1+n-j,min((ll)i-1,(ll)n-j))%mod)%mod;
        }
    cout<<ans<<endl;
    return 0;
}