結果
問題 |
No.444 旨味の相乗効果
|
ユーザー |
![]() |
提出日時 | 2025-03-31 17:25:25 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 861 ms / 2,500 ms |
コード長 | 3,177 bytes |
コンパイル時間 | 149 ms |
コンパイル使用メモリ | 82,160 KB |
実行使用メモリ | 79,952 KB |
最終ジャッジ日時 | 2025-03-31 17:26:31 |
合計ジャッジ時間 | 4,700 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 23 |
ソースコード
MOD = 10**9 + 7 def main(): import sys n, c = map(int, sys.stdin.readline().split()) a = list(map(int, sys.stdin.readline().split())) # Step 1: Compute elementary symmetric sums e_1 ... e_n mod MOD e = [0] * (n + 1) e[0] = 1 for num in a: num_mod = num % MOD # Iterate backwards to prevent overwriting for k in range(n, 0, -1): e[k] = (e[k] + num_mod * e[k-1]) % MOD # e now contains e_0 to e_n; e[1] to e[n] are needed # Step 2: Compute S_0 to S_{n-1} S = [0] * (n) S[0] = 1 for current_c in range(1, n): s = 0 for k in range(1, current_c + 1): # Compute the sign (-1)^(k+1) mod MOD sign = 1 if (k + 1) % 2 == 0 else -1 term = (e[k] * sign) % MOD term = (term * S[current_c - k]) % MOD s = (s + term) % MOD S[current_c] = s # Now handle S_c if c < n: sc = S[c] else: # Need to build the transition matrix and use matrix exponentiation # Build the transition matrix of size n x n mat = [[0] * n for _ in range(n)] # First row: coefficients from e_1 to e_n with signs for k in range(1, n+1): sign = 1 if (k + 1) % 2 == 0 else -1 coeff = (e[k] * sign) % MOD mat[0][k-1] = coeff # Other rows: identity matrix shift for i in range(1, n): mat[i][i-1] = 1 # Compute exponent and power the matrix exponent = c - (n - 1) # Function to multiply matrices with mod def multiply(A, B): res = [[0] * n for _ in range(n)] for i in range(n): for k in range(n): if A[i][k]: for j in range(n): res[i][j] = (res[i][j] + A[i][k] * B[k][j]) % MOD return res # Matrix exponentiation by squaring def matrix_pow(mat, power): result = [[0] * n for _ in range(n)] for i in range(n): result[i][i] = 1 while power > 0: if power % 2 == 1: result = multiply(result, mat) mat = multiply(mat, mat) power //= 2 return result powered_mat = matrix_pow(mat, exponent) # Initial vector is [S_{n-1}, S_{n-2}, ..., S_0] initial_vec = S[:n][::-1] # reversed # Multiply matrix with vector new_vec = [0] * n for i in range(n): for k in range(n): new_vec[i] = (new_vec[i] + powered_mat[i][k] * initial_vec[k]) % MOD sc = new_vec[0] # Compute sum a_i^c mod MOD sum_aic = 0 for num in a: num_mod = num % MOD if num_mod == 0 and c > 0: # a_i is 0, a_i^c is 0 if c >=1 term = 0 else: term = pow(num_mod, c, MOD) sum_aic = (sum_aic + term) % MOD answer = (sc - sum_aic) % MOD # Ensure positive answer = (answer + MOD) % MOD print(answer) if __name__ == '__main__': main()