結果
| 問題 | No.1847 Good Sequence |
| コンテスト | |
| ユーザー |
 LyricalMaestro
|
| 提出日時 | 2026-08-08 01:08:15 |
| 言語 | PyPy3 (7.3.17) |
| 結果 |
AC
|
| 実行時間 | 1,430 ms / 3,000 ms |
| + 502µs | |
| コード長 | 8,152 bytes |
| 記録 | |
| コンパイル時間 | 654 ms |
| コンパイル使用メモリ | 95,984 KB |
| 実行使用メモリ | 88,564 KB |
| 最終ジャッジ日時 | 2026-08-08 01:08:31 |
| 合計ジャッジ時間 | 15,308 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge1_1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 41 |
ソースコード
## https://yukicoder.me/problems/no/1847
MOD = 10 ** 9 + 7
MAX_INT = 10 ** 10
def main():
L, N, M = map(int, input().split())
K = list(map(int, input().split()))
L0 = L
forbidden_k_map = [MAX_INT] * (N + 1)
for k in K:
forbidden_k_map[k] = k
# 状態の数
state_list = []
for k in range(1, N + 1):
for j in range(1, k + 2):
state_list.append((k, j))
state_map = {}
for i, state in enumerate(state_list):
state_map[state] = i
state_count = len(state_list)
def prod(left, right):
new_matrix = [
[0 for _ in range(state_count)],
[[0 for _ in range(state_count)] for _ in range(state_count)]
]
# 0と0どうし
left_ = left[0]
right_ = right[0]
for l in range(state_count):
l_state, l_count = state_list[l]
for r in range(state_count):
r_state, r_count = state_list[r]
if l_state == r_state:
new_count = min(l_state + 1, l_count + r_count)
new_value = (left_[l] * right_[r]) % MOD
new_matrix[0][state_map[(l_state, new_count)]] += new_value
new_matrix[0][state_map[(l_state, new_count)]] %= MOD
else:
new_value = (left_[l] * right_[r]) % MOD
new_matrix[1][l][r] += new_value
new_matrix[1][l][r] %= MOD
# left:1, right:0
left_ = left[1]
right_ = right[0]
for l_l in range(state_count):
for l_r in range(state_count):
l_state, l_count = state_list[l_r]
for r in range(state_count):
r_state, r_count = state_list[r]
if l_state == r_state:
new_count = min(l_state + 1, l_count + r_count)
new_value = (left_[l_l][l_r] * right_[r]) % MOD
new_matrix[1][l_l][state_map[(l_state, new_count)]] += new_value
new_matrix[1][l_l][state_map[(l_state, new_count)]] %= MOD
else:
if forbidden_k_map[l_state] == l_count:
continue
new_value = (left_[l_l][l_r] * right_[r]) % MOD
new_matrix[1][l_l][r] += new_value
new_matrix[1][l_l][r] %= MOD
# left:0 ,right1
left_ = left[0]
right_ = right[1]
for l in range(state_count):
l_state, l_count = state_list[l]
for r_l in range(state_count):
for r_r in range(state_count):
r_state, r_count = state_list[r_l]
if l_state == r_state:
new_count = min(l_state + 1, l_count + r_count)
new_value = (left_[l] * right_[r_l][r_r]) % MOD
new_matrix[1][state_map[(l_state, new_count)]][r_r] += new_value
new_matrix[1][state_map[(l_state, new_count)]][r_r] %= MOD
else:
if forbidden_k_map[r_state] == r_count:
continue
new_value = (left_[l] * right_[r_l][r_r]) % MOD
new_matrix[1][l][r_r] += new_value
new_matrix[1][l][r_r] %= MOD
# left1: right1
left_ = left[1]
right_ = right[1]
for l_l in range(state_count):
base = 0
left_base = [0] * (N + 1)
for l_r in range(state_count):
base += left_[l_l][l_r]
base %= MOD
l_r_number, _ = state_list[l_r]
left_base[l_r_number] += left_[l_l][l_r]
left_base[l_r_number] %= MOD
for r_l in range(state_count):
r_l_number, r_l_count = state_list[r_l]
if forbidden_k_map[r_l_number] == r_l_count:
ans = left_base[r_l_number]
else:
ans = base
for mid in range(1, N + 1):
if forbidden_k_map[mid] == mid:
if mid != r_l_number:
ans -= left_[l_l][state_map[(mid, mid)]]
ans %= MOD
else:
y = r_l_number - r_l_count
if 1 <= y <= r_l_number + 1:
ans -= left_[l_l][state_map[(r_l_number, y)]]
ans %= MOD
for r_r in range(state_count):
new_matrix[1][l_l][r_r] += (ans * right_[r_l][r_r]) % MOD
new_matrix[1][l_l][r_r] %= MOD
return new_matrix
def prod_vec(matrix, vector):
new_vector = [0 for _ in range(state_count)]
# matrix 0
mat = matrix[0]
for vec_state in range(state_count):
vec_number, vec_count = state_list[vec_state]
for l in range(state_count):
l_number, l_count = state_list[l]
if vec_number == l_number:
new_count = min(vec_number + 1, l_count + vec_count)
new_vector[state_map[(l_number, new_count)]] += (mat[l] * vector[vec_state]) % MOD
new_vector[state_map[(l_number, new_count)]] %= MOD
else:
if forbidden_k_map[vec_number] == vec_count:
continue
new_vector[l] += (mat[l] * vector[vec_state]) % MOD
new_vector[l] %= MOD
# matrix1
mat = matrix[1]
for vec_state in range(state_count):
vec_number, vec_count = state_list[vec_state]
for l in range(state_count):
l_number, l_count = state_list[l]
if vec_number == l_number:
new_count = min(vec_number + 1, l_count + vec_count)
if forbidden_k_map[vec_number] == new_count:
continue
for r in range(state_count):
new_vector[r] += (mat[l][r] * vector[vec_state]) % MOD
new_vector[r] %= MOD
else:
if forbidden_k_map[vec_number] == vec_count:
continue
if forbidden_k_map[l_number] == l_count:
continue
for r in range(state_count):
new_vector[r] += (mat[l][r] * vector[vec_state]) % MOD
new_vector[r] %= MOD
return new_vector
# 1つ目の要素
matrix = [
[0 for _ in range(state_count)],
[[0 for _ in range(state_count)] for _ in range(state_count)]
]
for i in range(1, N + 1):
matrix[0][state_map[(i, 1)]] = 1
vector = None
while L > 0:
if L % 2 == 1:
if vector is None:
new_vector = [0 for _ in range(state_count)]
mat = matrix[0]
for l in range(state_count):
new_vector[l] += mat[l]
new_vector[l] %= MOD
mat = matrix[1]
for l in range(state_count):
l_number, l_count = state_list[l]
if forbidden_k_map[l_number] != l_count:
for r in range(state_count):
new_vector[r] += mat[l][r]
new_vector[r] %= MOD
vector = new_vector
else:
vector = prod_vec(matrix, vector)
matrix = prod(matrix, matrix)
L //= 2
answer = 0
for l in range(state_count):
l_number, l_count = state_list[l]
if forbidden_k_map[l_number] == l_count:
continue
answer += vector[l]
answer %= MOD
ans = pow(N, L0, MOD)
ans -= answer
ans %= MOD
print(ans)
if __name__ == "__main__":
main()