虽然考试的时候写不出来，但事后还是要看题解补一下的嗷！
看了题解真的觉得自己日常失智。
求每个区间不同的数个数的和。
不妨转换一下思维，考虑一个数x，存在于哪些区间中就对哪些区间有1的贡献。
一个数存在哪些区间中不是很好求，因为一个区间中可能有一个x，两个x......
所以再转换一下，求没有x的区间，最后用总数减去。
对于一个x，其存在的位置为p1，p2......pk。
两两之间的区间就是不存在x的区间。
设间隔距离为L，那么这中间的区间个数就是（L+1）*L/2.
k个数组中都是如此。
但是我们还要考虑k个数组之间产生的数组，L=n-pk+p1-1，乘k-1次即可。
L=p1 - 1和L=n - pk这两种情况算一次而不是k次（在两端）
然后取模小心。
#include<bits/stdc++.h> #define LL long long #define N 1000003 #define mod 1000000007 #define re register using namespace std; LL read() { LL x=0,f=1;char s=getchar(); while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} return x*f; } LL n,K; LL inv=500000004; LL a[N],b[N]; vector<LL>V[N]; LL f(LL x) { x%=mod;//!!!这一步!!! return (((x+1)*x)%mod*inv)%mod; } int main() { n=read();K=read(); for(int i=1;i<=n;++i)b[i]=a[i]=read(); sort(b+1,b+1+n); LL num=unique(b+1,b+1+n)-(b+1); for(int i=1;i<=n;++i) { a[i]=lower_bound(b+1,b+1+num,a[i])-b; V[a[i]].push_back(i); } LL ans=0; for(int i=1;i<=num;++i) { LL cnt=0; cnt+=f(V[i][0]-1); cnt%=mod; cnt+=f(n-V[i][V[i].size()-1]); cnt%=mod; LL sum=0; for(int j=1;j<V[i].size();++j) sum+=f(V[i][j]-V[i][j-1]-1),sum%=mod; sum=sum*K%mod; cnt=(sum+cnt)%mod; cnt+=((K-1)*f(n-V[i][V[i].size()-1]+V[i][0]-1))%mod; cnt%=mod; ans+=(f(n*K)-cnt+mod)%mod; ans%=mod; } printf("%lld ",ans); } /* */