正題

nowcoder 1103A

---

題目大意

有一個(gè)數(shù)組，將其復(fù)制k遍，求所有區(qū)間內(nèi)不同元素個(gè)數(shù)的和

---

解題思路

同一個(gè)區(qū)間內(nèi)有相同的數(shù)那么在最右邊的數(shù)計(jì)算貢獻(xiàn)

記 $r$ 為右邊第一個(gè)相等的數(shù)，那么貢獻(xiàn)就是到 $r$ 的距離乘上左邊的數(shù)字個(gè)數(shù)（有哪些區(qū)間可以讓這個(gè)數(shù)計(jì)算貢獻(xiàn)）

---

code

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define wyc 1000000007 #define N 100100 using namespace std; ll n,k,m,gg,ans,a[N],b[N],L[N],rs[N]; ll ksm(ll x,ll y) {ll z=1;while(y){if(y&1)z=z*x%wyc;x=x*x%wyc;y>>=1;}return z; } int main() {scanf("%lld%lld",&n,&k);for(ll i=1;i<=n;++i){scanf("%lld",&a[i]);b[i]=a[i];}sort(b+1,b+1+n);m=unique(b+1,b+1+n)-b-1;for(ll i=1;i<=n;++i)a[i]=lower_bound(b+1,b+1+m,a[i])-b;for(ll i=1;i<=m;++i)L[i]=n+1;for(ll i=n;i>0;--i){rs[i]=L[a[i]];L[a[i]]=i;}gg=ksm(2,wyc-2);for(ll i=1;i<=n;++i)ans=(ans+(i+n*(k-1)%wyc)%wyc*(rs[i]-i)%wyc)%wyc;for(ll i=1;i<=n;++i){if(rs[i]==n+1)rs[i]=n+L[a[i]];ans=(ans+(i+i+(k-2)*n%wyc)%wyc*(k-1)%wyc*gg%wyc*(rs[i]-i)%wyc)%wyc;}printf("%lld",ans);return 0; } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的复读数组（nowcoder 1103A）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。