C++(clang++11) 解法, 执行用时: 331ms, 内存消耗: 3352K, 提交时间: 2021-03-15 13:19:55

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

int k;
int f[111];

const int mod=1e9+7;

int a[111][111];
int g1[111],g2[111][111];

struct node
{
	int pos,tot;
}e[111];

void mul(int x[111],int y[111][111])
{
	memset(g1,0,sizeof(g1));
	for(int i=1;i<=k+1;++i)
		for(int j=1;j<=k+1;++j)
			g1[i]=(g1[i]+1ll*x[j]*y[j][i]%mod)%mod;
	memcpy(f,g1,sizeof(f));
}

void mul(int x[111][111],int y[111][111])
{
	memset(g2,0,sizeof(g2));
	for(int i=1;i<=k+1;++i)
		for(int j=1;j<=k+1;++j)
			for(int l=1;l<=k+1;++l)
				g2[i][j]=(g2[i][j]+1ll*x[i][l]*y[l][j]%mod)%mod;
	memcpy(a,g2,sizeof(a)); 
}

bool cmp(node p,node q)
{
	return p.pos<q.pos;
}

int main()
{
	int n,x,sum=0,t;
	long long m;
	scanf("%d%lld%d",&n,&m,&k);
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&x);
		t=e[x].tot;
		e[x].tot=sum+1;
		e[x].pos=i;
		sum=(sum-t+mod)%mod;
		sum=(sum+e[x].tot)%mod;
	}
	sort(e+1,e+k+1,cmp); 
	for(int i=1;i<=k;++i) f[i]=e[i].tot;
	f[k+1]=1;
	for(int i=1;i<k;++i) a[i+1][i]=1; 
	for(int i=1;i<=k+1;++i) a[i][k]=1;
	a[k+1][k+1]=1;
	while(m)
	{
		if(m&1) mul(f,a);
		mul(a,a);
		m>>=1;
	}
	int ans=0;
	for(int i=1;i<=k;++i) ans=(ans+f[i])%mod;
	printf("%d",ans);
}