正題

題目鏈接:https://ac.nowcoder.com/acm/contest/1103/A

---

題目大意

將一個(gè)長(zhǎng)度為$n$的數(shù)組復(fù)制成$k$份，然后每個(gè)區(qū)間的值是一個(gè)區(qū)間中不同的數(shù)的數(shù)量，求每個(gè)非空區(qū)間的值和。

---

解題思路

若一個(gè)區(qū)間長(zhǎng)度$>n$那么他們的值是固定的，所以我們可以先計(jì)算出這些區(qū)間的答案。

現(xiàn)在只需要考慮長(zhǎng)度$<n$的區(qū)間，我們講原數(shù)組復(fù)制一份放到后面后，我們用$f_i$表示第$i$個(gè)結(jié)尾的區(qū)間權(quán)值和。若不考慮$i$這個(gè)位置的貢獻(xiàn)那么$f_i=f_{i?1}$，$i$這個(gè)位置影響的區(qū)間是到上一個(gè)和它相同的位置$last$。也就是$f_i=f_{i?1}+i?last$。

當(dāng)$i>n$時(shí)我們不能計(jì)算左端點(diǎn)$>n$的區(qū)間，所以我們就改為$f_i=f_{i?1}+max\{n?last,0\}$即可。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=2e5+10,XJQ=1e9+7; ll n,k,a[N],ans,num,b[N],v[N]; ll power(ll x,ll b) {ll ans=1;while(b){if(b&1) ans=ans*x%XJQ;x=x*x%XJQ;b>>=1;}return ans; } 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);ll cnt=unique(b+1,b+1+n)-b-1;for(ll i=1;i<=n;i++){a[i]=a[i+n]=lower_bound(b+1,b+1+cnt,a[i])-b;if(!v[a[i]]) v[a[i]]=i,num++;}ans=num*n%XJQ*n%XJQ;ans=ans*max((k-2)*(k-1)%XJQ,0ll)%XJQ*power(2,XJQ-2)%XJQ;memset(v,0,sizeof(v));num=0;ll sum=0,z=0;for(ll i=1;i<=2*n;i++){ll last=0;if(v[a[i]]) last=v[a[i]];v[a[i]]=i;if(i>n) z+=max(n-last,0ll);else z+=i-last-(i>n);(sum+=z*(k-(i>n))%XJQ)%=XJQ;}printf("%lld",(ans+sum)%XJQ); }

總結(jié)

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

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