「题解」复读数组

[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;
}