Submission #9372464

---

Source Code Expand

#include <cstdio>
#include <cstring>
#include <algorithm>

typedef long long LL;
const int Mod = 1000000007;
const int MN = 25005, MK = 405;

inline int qPow(int b, int e) {
	int a = 1;
	for (; e; e >>= 1, b = (LL)b * b % Mod)
		if (e & 1) a = (LL)a * b % Mod;
	return a;
}

int N, K, M, A[MN];
int Ans, B1[MN], B2[MN];

inline int check() {
	static int lst[MK];
	int ok = 0, len = 0;
	for (int i = 1; i <= K; ++i) lst[i] = 0;
	for (int i = 1; i <= M; ++i) {
		len = std::min(len + 1, i - lst[A[i]]);
		lst[A[i]] = i;
		if (len == K) ok = 1;
	} return ok ? 0 : len;
}

inline void DP(int *B, int len) {
	static int f[MK], g[MK];
	for (int i = 1; i < K; ++i) f[i] = 0;
	f[len] = B[0] = 1;
	for (int i = 1; i <= N - M; ++i) {
		int Sum = 0;
		for (int j = K - 1; j >= 1; --j) {
			Sum -= (Sum += f[j]) >= Mod ? Mod : 0;
			g[j] = (Sum + (LL)(K - j + 1) * f[j - 1]) % Mod;
		}
		std::swap(f, g);
		Sum = 0;
		for (int j = 1; j < K; ++j) Sum -= (Sum += f[j]) >= Mod ? Mod : 0;
		B[i] = Sum;
	}
}

int main() {
	scanf("%d%d%d", &N, &K, &M);
	for (int i = 1; i <= M; ++i) scanf("%d", &A[i]);
	Ans = (LL)(N - M + 1) * qPow(K, N - M) % Mod;
	int chk = check();
	if (chk) {
		if (chk == M) {
			static int f[2][MK], g[2][MK];
			f[0][1] = K, f[1][1] = M > 1 ? 0 : K;
			for (int i = 2; i <= N; ++i) {
				int S0 = 0, S1 = 0;
				for (int j = K - 1; j >= 1; --j) {
					S0 -= (S0 += f[0][j]) >= Mod ? Mod : 0;
					S1 -= (S1 += f[1][j]) >= Mod ? Mod : 0;
					g[0][j] = (S0 + (LL)(K - j + 1) * f[0][j - 1]) % Mod;
					g[1][j] = (S1 + (LL)(K - j + 1) * f[1][j - 1] + (j >= M ? g[0][j] : 0)) % Mod;
				}
				std::swap(f, g);
			}
			int S1 = 0, C = 1;
			for (int j = 1; j < K; ++j) S1 -= (S1 += f[1][j]) >= Mod ? Mod : 0;
			for (int i = 0; i < M; ++i) C = (LL)C * (K - i) % Mod;
			Ans = (Ans - (LL)S1 * qPow(C, Mod - 2)) % Mod;
		} else {
			std::reverse(A + 1, A + M + 1);
			int lb = check(), rb = chk;
			DP(B1, lb), DP(B2, rb);
			for (int i = 0; i <= N - M; ++i)
				Ans = (Ans - (LL)B1[i] * B2[N - M - i]) % Mod;
		}
	}
	printf("%d\n", (Ans + Mod) % Mod);
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:48:29: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &N, &K, &M);
                             ^
./Main.cpp:49:49: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= M; ++i) scanf("%d", &A[i]);
                                                 ^

Judge Result