結果
問題 |
No.2651 [Cherry 6th Tune B] $\mathbb{C}$omplex комбинат
|
ユーザー |
|
提出日時 | 2024-12-15 02:03:47 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,190 ms / 2,500 ms |
コード長 | 2,359 bytes |
コンパイル時間 | 509 ms |
コンパイル使用メモリ | 82,256 KB |
実行使用メモリ | 147,828 KB |
最終ジャッジ日時 | 2024-12-15 02:04:59 |
合計ジャッジ時間 | 69,376 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 39 |
ソースコード
## https://yukicoder.me/problems/no/2651 MOD = 998244353 def solve(N, xy): z2_list = [] for x, y in xy: x_ = (pow(x, 2, MOD) - pow(y, 2, MOD)) % MOD y_ = (x * y) % MOD y_ *= 2 y_ %= MOD z2_list.append((x_, y_)) z_abs_list = [] for x, y in xy: s = pow(x, 2, MOD) s += pow(y, 2, MOD) s %= MOD z_abs_list.append(s) # 1 / |z|^2 の累積和計算 cum_inv_z_abs2_list = [0] * N cum_inv_z_abs2 = 0 for i in range(N): cum_inv_z_abs2_list[i] = cum_inv_z_abs2 cum_inv_z_abs2 += pow(z_abs_list[i], (MOD - 2), MOD) cum_inv_z_abs2 %= MOD # |z|^2 の累積和計算 cum_z_abs2_list = [0] * N cum_z_abs2 = 0 for i in range(N): cum_z_abs2_list[i] = cum_z_abs2 cum_z_abs2 += z_abs_list[i] cum_z_abs2 %= MOD # cum_a_list = cum_a_list = [0] * N cum_a = 0 for i in range(N): cum_a_list[i] = cum_a a = z2_list[i][0] a *= pow(z_abs_list[i], MOD - 2, MOD) a %= MOD cum_a += a cum_a %= MOD cum_b_list = [0] * N cum_b = 0 for i in range(N): cum_b_list[i] = cum_b a = z2_list[i][1] a *= pow(z_abs_list[i], MOD - 2, MOD) a %= MOD cum_b += a cum_b %= MOD answer = 0 for i in range(N): ans = (z_abs_list[i] * cum_inv_z_abs2_list[i]) % MOD ans += (cum_z_abs2_list[i] * pow(z_abs_list[i], MOD - 2, MOD)) % MOD ans %= MOD ans_re1 = (z2_list[i][0] * pow(z_abs_list[i], MOD - 2, MOD)) % MOD ans_re1 *= cum_a_list[i] ans_re1 %= MOD ans_re2 = (z2_list[i][1] * pow(z_abs_list[i], MOD - 2, MOD)) % MOD ans_re2 *= cum_b_list[i] ans_re2 %= MOD ans_re = (ans_re1 + ans_re2) % MOD ans_re *= -2 ans_re %= MOD answer += ans answer %= MOD answer += ans_re answer %= MOD return answer def main(): T = int(input()) answers = [] for _ in range(T): N = int(input()) xy = [] for _ in range(N): x, y = map(int, input().split()) xy.append((x, y)) ans = solve(N, xy) answers.append(ans) for ans in answers: print(ans) if __name__ == "__main__": main()