rt，下面是一份超时 116 分代码。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int f[1000009];
int a[1000009];
int nxt[1000009];
int c[1000009];
signed main(){
	std::ios::sync_with_stdio(0);
	int n;
	cin>>n;
	int m;cin>>m;
	for(int i=1;i<=m;i++){
		cin>>a[i];
	}
	nxt[0]=-1;
	f[1]=n;
	for(int i=2;i<=m;i++){
		f[i]=f[i-1]*n+n;
		int z;
		z=i-1;
		while(z>-1){
			z=nxt[z];
			if(a[z+1]==a[i]&&!nxt[i]){
				nxt[i]=z+1;
break;
			}
			//cout<<z<<endl;
		}
		f[i]-=c[nxt[i-1]+1]+f[nxt[i-1]+1]-f[nxt[i]];
		c[i]=c[nxt[i-1]+1]+f[nxt[i-1]+1]-f[nxt[i]];
		f[i]+=(int)(1e9+7)*(int)(1e9+7);
		f[i]%=(int)(1e9+7);
	}
	for(int i=1;i<=m;i++){
		cout<<f[i]<<endl;
	}
	cin>>n;
	return 0;
}

但是，稍微改一下，结果截然不同（最慢点 100+ms）:

#include<bits/stdc++.h>
using namespace std;
#define int long long
int f[1000009];
int a[1000009];
int nxt[1000009];
int c[1000009];
signed main(){
	std::ios::sync_with_stdio(0);
	int n;
	cin>>n;
	int m;cin>>m;
	for(int i=1;i<=m;i++){
		cin>>a[i];
	}
	nxt[0]=-1;
	f[1]=n;
	for(int i=2;i<=m;i++){
		f[i]=f[i-1]*n+n;
		int z;
		z=i-1;
		while(z>-1){
			z=nxt[z];
			if(a[z+1]==a[i]&&!nxt[i]){
				nxt[i]=z+1;
break;
			}
			//cout<<z<<endl;
		}
		f[i]-=c[nxt[i-1]+1]+f[nxt[i-1]+1]-f[nxt[i]];
		c[i]=c[nxt[i-1]+1]+f[nxt[i-1]+1]-f[nxt[i]];
		f[i]+=(int)(1e9+7)*(int)(1e9+7);
		f[i]%=(int)(1e9+7);
	}
	for(int i=1;i<=m;i++){
		cout<<f[i]<<"\n";
	}
	cin>>n;
	return 0;
}

我记得 endl 没这么慢啊，至少 $10^6$ 能跑。