結果
問題 | No.1510 Simple Integral |
ユーザー |
![]() |
提出日時 | 2021-05-14 23:23:21 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 604 ms / 2,000 ms |
コード長 | 1,275 bytes |
コンパイル時間 | 283 ms |
コンパイル使用メモリ | 12,544 KB |
実行使用メモリ | 44,640 KB |
最終ジャッジ日時 | 2024-10-02 05:08:53 |
合計ジャッジ時間 | 29,237 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 43 |
ソースコード
import numpy as np MOD = 998_244_353 def main(A): # 1 / (x^2+1)^n の留数 R = np.zeros(200, np.int64) R[0] = 1 for i in range(1, 200): R[i] = R[i-1] * pow(2*i,-1,MOD) % MOD * (i+i-1) % MOD R = np.append(0, R) def residue(a): # f(ax) の留数を求めてから、a で割ればよい inv_a = pow(int(a),-1,MOD) coef = pow(inv_a,2*len(A)-1,MOD) B = A * inv_a % MOD # 重複度 n = np.sum(A == a) B = B * B - 1 B %= MOD # z = x^2 + 1 に関する展開 f = np.array([1] + [0] * n, np.int64) for b in B[B != 0]: # (z + b)^{-1} をかける c = pow(int(b),-1,MOD) f = f * c % MOD c = (-c) % MOD # 1 - cz で割る for i in range(1,len(f)): f[i] += c * f[i-1] f[i] %= MOD res = 0 for i in range(n): # f[i](x^2+1)^i / (x^2+1)^n の residue k = n - i res += f[i] * R[k] % MOD res %= MOD return res * coef % MOD ans = 0 for x in np.unique(A): res = residue(x) ans += res return ans % MOD input() A = np.array(input().split(), np.int64) print(main(A))