复读数组

本文主要是介绍复读数组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

复读数组

题解

我们可以枚举所有区间，再依次枚举所有不含x的区间，将其减去即可。我们可以依次枚举x在整个数组。
设x在这个的数组中出现的位置为。那么x的每一次相邻的出现之间的所有区间都是满足条件的。设，那么不包含x的区间个数就为。我们再枚举n的区间，加上它所重复的即可。

源码

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<stack>
#include<vector>
#include<queue>
#include<map>
#define MAXN 100005
using namespace std;
typedef long long LL;
const LL mo=1e9+7;
const LL Inv2=5e8+4;
LL n,k,b[MAXN],tot,ans,num;
LL p[MAXN];
bool c[MAXN];
map<LL,LL> mp;
#define gc() getchar()
template<typename _T>
inline void read(_T &x)
{_T f=1;x=0;char s=gc();while(s>'9'||s<'0'){if(s=='-')f=-1;s=gc();}while(s>='0'&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=gc();}x*=f;
}
LL f(LL x)
{x%=mo;return x*(x+1)%mo*Inv2%mo;
}
int main()
{ read(n);read(k);for(LL i=1;i<=n;i++){read(b[i]);if(!mp[b[i]]) mp[b[i]]=++tot;b[i]=mp[b[i]];}num=f(n*k);ans=num*tot%mo;for(LL i=1;i<=n;i++){if(p[b[i]])ans=(ans-f(i-p[b[i]]-1)*k%mo+mo)%mo;else c[i]=true;p[b[i]]=i;}for(int i=1;i<=n;i++)if(c[i]){ans=(ans-f(i+n-p[b[i]]-1)*(k-1)%mo+mo)%mo;ans=(ans-f(i-1)+mo)%mo;ans=(ans-f(n-p[b[i]])+mo)%mo;}printf("%lld",ans);return 0;
}

谢谢！！！

这篇关于复读数组的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---