链接

点击跳转

题解

这题情况有点多，较繁

大体的思路应该很容易想到，就是不停的进行首位配对

关键是特殊情况

首先，自身内部可能会自行去掉一些，自身去掉一些之后，整个序列可能会变成空序列

再者，当$m=1$的时候也要特判一下

代码

#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define iinf 0x3f3f3f3f #define linf (1ll<<60) #define eps 1e-8 #define maxn 1000010 #define maxe 1000010 #define cl(x) memset(x,0,sizeof(x)) #define rep(_,__) for(_=1;_<=(__);_++) #define em(x) emplace(x) #define emb(x) emplace_back(x) #define emf(x) emplace_front(x) #define fi first #define se second #define de(x) cerr<<#x<<" = "<<x<<endl using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; ll read(ll x=0) { ll c, f(1); for(c=getchar();!isdigit(c);c=getchar())if(c=='-')f=-f; for(;isdigit(c);c=getchar())x=x*10+c-0x30; return f*x; } pll lis1[maxn], lis2[maxn]; ll n, m, k, a[maxn], ans; int main() { ll i, j, tot=0; n=read(), k=read(), m=read(); rep(i,n)a[i]=read(); rep(i,n) { if(a[i]==lis1[tot].fi)lis1[tot].se++; else lis1[++tot]=pll(a[i],1); lis1[tot].se%=k; if(lis1[tot].se==0)tot--; } rep(i,tot)ans+=m*lis1[i].se; if(tot==0){cout<<0;return 0;} if(m==1){cout<<ans;return 0;} rep(i,tot)lis2[i]=lis1[i]; for(i=tot,j=1;i>j;i--,j++) { ll l=(lis1[i].se+lis2[j].se); if(lis1[i].fi==lis2[j].fi and l%k==0)ans-=(m-1)*l; else break; } if(i>j) { ll l=(lis1[i].se+lis2[j].se); if(lis1[i].fi==lis2[j].fi)ans-=(m-1)*(l-l%k); cout<<ans; return 0; } ll l=lis1[i].se; if(l*m%k==0)ans=0; else ans-=l*m/k*k; cout<<ans; return 0; }