原题链接:F-小红的数组回文值
题意:给长度为n的数组,求这个数组的任意子序列的回文值总和,回文值定义为一个子序列应该元素相同,但是不相同的位置数量。
思路:范德蒙恒等式优化组合数。最暴力的思路是枚举出全部的子序列,然后暴力的计算回文值,但是明显会超时。从算贡献的角度来思考,对于每一对不相同的元素可以计算出这一对对全部子序列的贡献,例如说 i,j这二个位置不相同,如果它们在同一个子序列里面,就是在[1,i-1]和[j+1,n],这二个区间里面选择相同数量的数,再在[i+1,j-1]这个区间里面随便的取数,那么就可以的到答案的组合数公式。,根据范德蒙恒等式的性质,,所以答案就是。
//冷静,冷静,冷静
//调不出来就重构
//#pragma GCC optimize(2)
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#define count2(x) __builtin_popcountll(x)
#define is2(x) __builtin_ffsll(x)
#define endl '\n'
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pii;
const int N=1e6+10,mod=1000000007;
ll p[N],fact[N],infact[N];
ll ksm(ll a,ll b)
{ll ans=1;do{if(b&1)ans*=a;a*=a;b>>=1;a%=mod;ans%=mod;}while(b);return ans;
}
ll C(ll a,ll b)
{return fact[a]%mod*infact[b]%mod*infact[a-b]%mod;
}
void Jiuyuan()
{ll n;cin>>n;fact[0]=infact[0]=1;for(int i=1;i<=n;i++){fact[i]=i*fact[i-1];fact[i]%=mod;infact[i]=ksm(i,mod-2)*infact[i-1];infact[i]%=mod;}for(int i=1;i<=n;i++){cin>>p[i];}ll ans=0;for(int i=1;i<=n;i++){for(int j=i;j<=n;j++){if(p[i]!=p[j]){ans=ans+(C(i-1+n-j,min(i-1ll,n-j))%mod*ksm(2,j-i-1)%mod)%mod;ans%=mod;}}}cout<<ans<<endl;
}
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);ll T=1;
// cin>>T;while(T--){Jiuyuan();}return 0;
}