题意
有一长为 (n) 的序列 (a),(a_iin [1,k]cap mathbf{N})。你要在后面添 (m) 个数((a_iin [1,k]cap mathbf{N})),使得新序列的本质不同子序列个数最大。模 (998244353)。(nleq 10^6),(kleq 100),(mleq 10^{18})。
题解
首先考虑如何求一个序列的本质不同子序列个数:设 (f_i) 为考虑前 (i) 个数的本质不同子序列个数,如果没有出现相同数字,(f_{i+1}=2f_i),如果在 (t) 处出现过相同数字,则 (f_{i+1}=2f_i-f_{t-1})(前 (t-1) 个数加上最后一个和前 (i) 个数加上最后一个会重)。
加新的数字时,肯定优先加要减的 (f) 小的数字(要是这个数放在之后加,前面的 ( imes 2) 次数很多的地方用要减的 (f) 大的数显然不优),也就是出现最近一次出现最早的数字。于是到了之后,有 (f_{i}=2f_{i-1}-f_{i-k-1}),于是矩阵乘法优化常系数齐次线性递推。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
ll getint(){
ll ans=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
ans=ans*10+c-'0';
c=getchar();
}
return ans*f;
}
const int N=1e6+10,K=105,mod=1e9+7;
int a[N],n,k;
int lst[K];
bool v[K];
int b[K];
ll m;
struct mat{
int a[K][K];
mat(){memset(a,0,sizeof(a));}
void init1(){
for(int i=0;i<=k;i++)a[i][i]=1;
}
void init(){
for(int i=0;i<k;i++)a[i][i+1]=1;
a[k][0]=mod-1;a[k][k]=2;
}
int * operator[](int x){
return a[x];
}
};
mat operator* (mat &x,mat &y){
mat z;
for(int i=0;i<=k;i++){
for(int j=0;j<=k;j++){
for(int l=0;l<=k;l++){
z[i][j]=(z[i][j]+x[i][l]*1ll*y[l][j])%mod;
}
}
}
return z;
}
int qpow(ll m){
mat x,ans;
ans.init1();
x.init();
// for(int i=0;i<=k;i++){
// for(int j=0;j<=k;j++)cerr<<ans[i][j]<<" ";
// cerr<<endl;
// }cerr<<endl;
// for(int i=0;i<=k;i++){
// for(int j=0;j<=k;j++)cerr<<x[i][j]<<" ";
// cerr<<endl;
// }cerr<<endl;
while(m){
if(m&1)ans=ans*x;
x=x*x;
m>>=1;
}
// for(int i=0;i<=k;i++){
// for(int j=0;j<=k;j++)cerr<<x[i][j]<<" ";
// cerr<<endl;
// }cerr<<endl;
int res=0;
for(int i=0;i<=k;i++)
res=(res+b[i]*1ll*ans[k][i])%mod;
return res;
}
signed main(){
n=getint(),m=getint(),k=getint();
for(int i=1;i<=n;i++)a[i]=getint();
int f=1;
for(int i=1;i<=n;i++){
int t=lst[a[i]];
lst[a[i]]=f;
f=(f=f*2ll-t+mod)%mod;
}
int tmp=k;
b[tmp]=f;
for(int i=n;i>=1;--i){
if(!v[a[i]])b[--tmp]=lst[a[i]];
v[a[i]]=1;
}
if(m<=1e6){
queue<int>q;
for(int i=0;i<=k;i++)q.push(b[i]);
for(int i=0;i<m;i++){
q.push((q.back()*2ll-q.front()+mod)%mod);
q.pop();
}
cout<<q.back()-1<<endl;
}else{
int ans=qpow(m);
cout<<ans-1<<endl;
}
}