結果
問題 |
No.1521 Playing Musical Chairs Alone
|
ユーザー |
![]() |
提出日時 | 2025-03-20 21:05:10 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 514 ms / 2,000 ms |
コード長 | 1,639 bytes |
コンパイル時間 | 146 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 77,148 KB |
最終ジャッジ日時 | 2025-03-20 21:05:19 |
合計ジャッジ時間 | 6,660 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
MOD = 10**9 + 7 def main(): import sys N, K, L = map(int, sys.stdin.readline().split()) # 预处理cnt数组 cnt = [0] * N for d in range(N): if d == 0: cnt[d] = L // N else: if d > L: cnt[d] = 0 else: cnt[d] = (L - d) // N + 1 cnt[d] %= MOD # 构造转移矩阵 mat = [[0] * N for _ in range(N)] for i in range(N): for j in range(N): d = (j - i) % N mat[i][j] = cnt[d] # 矩阵快速幂 def multiply(A, B): n = len(A) result = [[0]*n for _ in range(n)] B_T = list(zip(*B)) # transpose B to get columns as rows for i in range(n): row_A = A[i] for j in range(n): total = 0 for k in range(n): total += row_A[k] * B_T[j][k] if total >= MOD: total %= MOD result[i][j] = total % MOD return result def matrix_pow(mat, power): n = len(mat) # 初始化为单位矩阵 result = [[0]*n for _ in range(n)] for i in range(n): result[i][i] = 1 current = mat while power > 0: if power % 2 == 1: result = multiply(result, current) current = multiply(current, current) power //= 2 return result mat_k = matrix_pow(mat, K) # 输出第0行的各个元素 for j in range(N): print(mat_k[0][j] % MOD) if __name__ == '__main__': main()