oj.uz

Submission #541655

# Submission time Handle Problem Language Result Execution time Memory
541655 2022-03-24T02:02:25 Z colazcy Klavir (COCI17_klavir) C++17
160 / 160
 133 ms 27936 KB 
#include <cstdio>
#include <cassert>
#include <cctype>
#include <vector>
#include <tuple>
#include <algorithm>
#define let const auto
#define rep(name,beg,end) for(auto lim_##name = end,name = beg;name <= lim_##name;name++)
#define per(name,beg,end) for(auto lim_##name = end,name = beg;name >= lim_##name;name--)
#define repn(lim) for(auto REPN_lIM = lim,REPN = 1;REPN <= REPN_lIM;REPN++)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define trace() debug("line : %d, Function : %s\n",__LINE__,__FUNCTION__)
constexpr int maxn = 1e6 + 10,mod = 1e9 + 7;
int read(){
	int x = 0,f = 1; char c = std::getchar();
	while(!std::isdigit(c))f = c == '-' ? -1 : 1,c = std::getchar();
	while(std::isdigit(c))x = x * 10 + c - '0',c = std::getchar();
	return x * f;
}
template <typename T>
void print(T x){
	char buf[33];
	int top = 0;
	do{
		buf[++top] = x % 10 + '0';
		x /= 10;
	}while(x);
	per(i,top,1)std::putchar(buf[i]);
	std::putchar('\n');
}
int n,m,str[maxn],pi[maxn],pw[maxn],ans[maxn];
void kmp(){
	int j = 0;
	rep(i,2,m){
		while(j && str[j + 1] != str[i])j = pi[j];
		if(str[j + 1] == str[i])j++;
		pi[i] = j;
	}
}
int main(){
	// std::freopen("klavir.in","r",stdin);
	// std::freopen("klavir.out","w",stdout);
	n = read(),m = read();
	rep(i,1,m)str[i] = read();
	kmp();
	pw[0] = 1;
	rep(i,1,m)pw[i] = 1ll * n * pw[i - 1] % mod;
	rep(i,1,m){
		ans[i] = (ans[pi[i]] + pw[i]) % mod;
	}
	rep(i,1,m)print(ans[i]);
	std::fclose(stdin);
	std::fclose(stdout);
	return 0;	
}

Subtask #1
16.0 / 16.0

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

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 296 KB Output is correct

Subtask #3
16.0 / 16.0

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

Subtask #4
16.0 / 16.0

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

Subtask #5
16.0 / 16.0

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

Subtask #6
16.0 / 16.0

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

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3028 KB Output is correct
2 Correct 69 ms 24784 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 27776 KB Output is correct
2 Correct 72 ms 24780 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 27816 KB Output is correct
2 Correct 69 ms 24768 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 27936 KB Output is correct
2 Correct 80 ms 24780 KB Output is correct