Submission #91484

#	Time	Username	Problem	Language	Result	Execution time	Memory
91484		jangwonyoung	Klavir (COCI17_klavir)	C++14	160 / 160	183 ms	53996 KiB

klavir

#include<iostream>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int M=1e6+1;
int m;
int n;
int a[M];
int f[M];
ll x[M],y[M];
ll e[M];
ll pw(ll x,ll y){
	if(y==0) return 1;
	if(y%2) return x*pw(x,y-1)%mod;
	ll res=pw(x,y/2);
	return res*res%mod;
}
int main(){
	ios::sync_with_stdio(false);
	cin >> n >> m;
	f[0]=-1;
	for(int i=1; i<=m ;i++){
		cin >> a[i];
		int cur=f[i-1];
		while(cur>=0 && a[cur+1]!=a[i]) cur=f[cur];
		f[i]=cur+1;
	}
	x[0]=1;y[0]=0;
	x[1]=1;y[1]=n;
	for(int i=2; i<=m ;i++){
		x[i]=(n*x[i-1]+(mod-n)*x[f[i-1]]+x[f[i]])%mod;
		y[i]=(n*y[i-1]+(mod-n)*y[f[i-1]]+y[f[i]])%mod;
	}
	e[0]=y[n]*pw(x[n],mod-2)%mod;
	for(int i=1; i<=m ;i++){
		e[i]=(x[i]*e[0]+mod-y[i])%mod;
		cout << (e[0]-e[i]+mod)%mod << '\n';
	}
}

• Subtask 1: 16 / 16
• Subtask 2: 16 / 16
• Subtask 3: 16 / 16
• Subtask 4: 16 / 16
• Subtask 5: 16 / 16
• Subtask 6: 16 / 16
• Subtask 7: 16 / 16
• Subtask 8: 16 / 16
• Subtask 9: 16 / 16
• Subtask 10: 16 / 16