oj.uz

Submission #91484

# Submission time Handle Problem Language Result Execution time Memory
91484 2018-12-27T17:17:21 Z jangwonyoung Klavir (COCI17_klavir) C++14
160 / 160
 183 ms 53996 KB 
#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.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 692 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 740 KB Output is correct
2 Correct 2 ms 812 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 812 KB Output is correct
2 Correct 2 ms 812 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 812 KB Output is correct
2 Correct 2 ms 812 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 812 KB Output is correct
2 Correct 2 ms 812 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 5268 KB Output is correct
2 Correct 158 ms 40984 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 45868 KB Output is correct
2 Correct 183 ms 45868 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 49948 KB Output is correct
2 Correct 165 ms 49948 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 53996 KB Output is correct
2 Correct 164 ms 53996 KB Output is correct