[toc]
题目链接:牛客 1103 A
题目比较简单,就吧代码放在这了。
#include<cstdio>
#include<algorithm>
using std::sort;
using std::unique;
using std::lower_bound;
#include<vector>
using std::vector;
#define reg register
typedef long long ll;
#define MOD 1000000007ll
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
reg bool f=false;
reg char ch=getchar();
reg int res=0;
while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar();
while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
return f?-res:res;
}
const int MAXN=100000+5;
int n;
ll K,Inv;
int a[MAXN];
int fir[MAXN];
int pre[MAXN];
vector<int> V;
inline void Read(void);
inline void Work(void);
inline ll pow(reg ll,reg ll,reg ll);
inline ll Calc(reg ll);
int main(void){
Read();
Work();
return 0;
}
inline void Read(void){
n=read(),K=read();
for(reg int i=1;i<=n;++i)
a[i]=read();
return;
}
inline void Work(void){
Inv=pow(2,MOD-2,MOD);
for(reg int i=1;i<=n;++i)
V.push_back(a[i]);
sort(V.begin(),V.end());
V.erase(unique(V.begin(),V.end()),V.end());
for(reg int i=1;i<=n;++i)
a[i]=lower_bound(V.begin(),V.end(),a[i])-V.begin()+1;
reg ll len=V.size(),f1=0,f2=0,f3=0;
for(reg int i=1;i<=n;++i){
if(!pre[a[i]]){
f3=(f3+Calc(i-1))%MOD;
fir[a[i]]=i;
}
else
f1=(f1+Calc(i-pre[a[i]]-1))%MOD;
pre[a[i]]=i;
}
for(reg int i=1;i<=len;++i)
if(pre[i]){
f3=(f3+Calc(n-pre[i]))%MOD;
f2=(f2+Calc(n+fir[i]-pre[i]-1))%MOD;
}
ll sum=(f1*K%MOD+f2*(K-1)%MOD+f3)%MOD;
printf("%lld\n",(len*Calc(n*K%MOD)%MOD-sum+MOD)%MOD);
return;
}
inline ll pow(reg ll x,reg ll exp,reg ll mod){
reg ll res=1;
while(exp){
if(exp&1)
res=res*x%mod;
x=x*x%mod;
exp>>=1;
}
return res;
}
inline ll Calc(reg ll n){
return n*(n+1)%MOD*Inv%MOD;
}
近期评论