제출 #541655

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
541655		colazcy	Klavir (COCI17_klavir)	C++17	160 / 160	133 ms	27936 KiB

klavir

#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 / 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