复读数组题解_牛客博客

有一个长为 $n×k$ 的数组，它是由长为 $n$ 的数组 $A_1$ , $A_2$ ,..., $A_n$ 重复 $k$ 次得到的。
定义这个数组的一个区间的权值为它里面不同的数的个数，现在，你需要求出对于这个数组的每个非空区间的权值之和。
答案对 $10^9+7$ 取模。

注意到计算每一个区间的影响是很难的,因为我们能表示一个区间颜色种类数的方法是最快 $O(lenlog_2len)$ 的

$\text{HH}$ 的项链

而这道题 $len\le 10^{14}$ 让我们放弃

这又是一个套路了，既然我们不好直接求，那么拆分问题

给一个相似的例子

求 $a_1,a_2\cdots,a_n$ 两两异或的和

肯定正着做不好做，但考虑到，这个问题在 $a_i\in\{0,2^k\}$ 时就很好做

因此想到拆位

对于这道题也是一样，考虑计算每种颜色贡献的区间

仿佛也不好做，但正难则反，计算每种颜色不会贡献的区间很简单

那就是相邻的两个颜色间的所有区间

对 $n$ 的序列我们可以轻易用一次扫描 $O(n)$ 通过记录每个颜色上次出现的位置 $last_i$ 利用组合数求出

但对 $n*k$ 的呢

考虑有些部分重复求了

红色的被夹在区间中间的部分有 $K$ 个

绿色蓝色各有 $1$ 个

绿蓝拼在一起的有 $K-1$ 个

因此我们只需要求 $n/2n$ 的区间把色块拼起来就可以了

最后说明一下

长度 $\le len$ 区间个数 $\frac{len(len+1)}{2}$

#include<bits/stdc++.h>
#define re register
#define N 100001
#define INF 0x3f3f3f3f
#define mod 1000000007ll
using namespace std;
inline char nc(){
    static char buf[1048576],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1048576,stdin),p1==p2)?EOF:*p1++;
}
#define getchar nc
template<typename _int>
inline void read(re _int& x){
    re char opt;re _int flag=1,res=0;
    while((opt=getchar())<'0'||opt>'9')if(opt=='-')flag=-1;
    while(opt>='0'&&opt<='9'){res=(res<<3)+(res<<1)+opt-'0';opt=getchar();}
    x=res*flag;
}
typedef long long ll;
int a[N<<1],pos[N],t[N],tot,l[N<<1];
ll ans,n,k;
inline ll f(re ll x){return x*(x+1)%mod*500000004ll%mod;}
inline void Read(void){
    re int i;read(n);read(k);
    for(i=1;i<=n;++i){read(a[i]);t[i]=a[i];}
    sort(t+1,t+n+1);tot=unique(t+1,t+n+1)-(t+1);
    for(i=1;i<=n;++i){a[i]=lower_bound(t+1,t+tot+1,a[i])-t;a[i+n]=a[i];}
}
inline void Solve(void){
    re int i;re ll self,sum,len,left,right;
    ans=f(1ll*n*k%mod)*tot%mod;
    self=0;
    for(i=1;i<=n;++i){
        l[i]=pos[a[i]];pos[a[i]]=i;
        if(l[i]+1==i||!l[i])continue;len=1ll*i-l[i]-1ll;
        self=(self+f(len))%mod;
    }
    for(i=1;i<=tot;++i)pos[i]=0;
    left=0;
    for(i=1;i<=n;++i){
        l[i]=pos[a[i]];pos[a[i]]=i;
        if(l[i]||l[i]+1==i)continue;len=1ll*i-l[i]-1ll;
        left=(left+(1ll*len*(len+1ll)>>1ll))%mod;
    }
    for(i=1;i<=tot;++i)pos[i]=n+1;
    right=0;
    for(i=n;i>=1;--i){
        l[i]=pos[a[i]];pos[a[i]]=i;
        if(l[i]!=n+1||l[i]-1==i)continue;len=1ll*l[i]-i-1ll;
        right=(right+(1ll*len*(len+1ll)>>1ll))%mod;
    }
    for(i=1;i<=tot;++i)pos[i]=0;
    sum=0;
    for(i=1;i<=(n<<1);++i){
        l[i]=pos[a[i]];pos[a[i]]=i;
        if(l[i]+1==i)continue;len=1ll*i-l[i]-1ll;
        sum=(sum+(1ll*len*(len+1ll)>>1ll))%mod;
    }
    sum=((sum-self*2ll%mod-left)%mod+mod)%mod;
    ans=(((ans-1ll*k*self%mod+mod)%mod-sum*(k-1ll)%mod-left-right)%mod+mod)%mod;
    printf("%lld\n",(ans%mod+mod)%mod);
}
int main(void){
    Read();Solve();
    return 0;
}