abc 169 (python)

Eまで5完。Fが形式的冪級数だと気づきさえすれば６完できたのに。
Bは０が後ろにあるケースがサンプルにあったからすぐ修正できた。sort したら前から10**18 を超えたら -1 を出力するようにプログラミングしてよい。python は10**18の計算をしてもエラー吐かないから素晴らしい。

Cは初めて decimal.Decimal を使った。python の誤差については、整数だと10**15 くらいまで、少数だと2進数表記するために 2.51 が 2.50999999 とかになって100倍したりすると答えがずれてくる。Decimal('2.51') とすると、文字列として 2.51 を１０進法表記で計算してくれるので２８桁ぐらいまで正確に計算してくれる。

Dは見た瞬間に素因数分解する奴とわかる。素因数分解してからは、例えば 576 とすると、
576 = 2**6 * 3**2 となり、2**6 は 2*4*8 とできるので３つ、3**2 は 3 よりは大きく 3*(3**2) よりは小さいので1つ作れて答えは 4 となる。つまり、Nを素因数分解して、
N = P1**k1 * P2**k2 * P3 ** k3*... と書けるとき（P1,P2,P3は異なる素数）
答えには m*(m+1)//2 <= k1 < (m+1)*(m+2)//2 となる整数m を足していけばいいと分かる。

Eは Ai <= Xi <= Bi を単なる直線として紙に書いていけば、中央値の候補となるうる範囲が直線から浮き上がってくるのではないかと思う。Nが奇数のときは sort したときに N//2+1 番目に来ることができる最大値ー最小値+1を求めるだけでよく、偶数の時は中央値が N//2 番目の数と N//2+1 番目の数の平均なので、
N//2+1 番目の最大値+N//2 番目の最大値 - (N//2+1 番目の最小値+N//2 番目の最小値)+1
で求まる。

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n = int(readline())
import numpy as np
ab = np.array(read().split(),np.int32)
a = ab[::2]
b = ab[1::2]
a.sort()
b.sort()
if n%2 == 1:
  L = a[n//2] #N//2+1 番目に来うる最大値
  R = b[n//2] #N//2+1 番目に来うる最小値
  ans = R-L+1
else:
  LL = a[n//2-1] #N//2 番目に来うる最小値
  LR = b[n//2-1] #N//2 番目に来うる最大値
  RL = a[n//2] #N//2+1 番目に来うる最小値
  RR = b[n//2] #N//2+1 番目に来うる最大値
  ans = RR+LR-LL-RL+1
print(ans)

Fは形式的冪級数さえわかれば、
サンプル１の場合は (2+x**2)*(2+x**2)*(2+x**4) を展開したときに x**4 につく係数を求める問題に帰着できる。
形式的冪級数を表現するには、例えば x**3 + 2*x**2 + 5 とすると、リスト上で、
list = [5,0,2,3] としてやればよい。
そして今回の *(2+x**k) をどうするかというと、*(2+x**k) = *2 + *x**k なので

2 → list の要素を全て２倍する（numpy使うと楽)

x**k → list の要素をすべて右に k こずらす

とすればよい。

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np
mod = 998244353

n,s = map(int,readline().split())
a = list(map(int,readline().split()))
d = np.zeros(3001, np.int64)
d[0] = 1
for i in a:
  dd = [0]*i + list(d) #右にｋ個ずらす
  d = d*2                 #リストを２倍する
  d += dd[:3001]     #足し合わせる
  d %= mod
print(d[s])