結果

問題 No.3169 [Cherry 7th Tune] Desire for Approval
ユーザー dp_ijk
提出日時 2025-05-30 22:46:49
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,573 ms / 7,000 ms
コード長 13,272 bytes
コンパイル時間 1,031 ms
コンパイル使用メモリ 82,104 KB
実行使用メモリ 161,312 KB
最終ジャッジ日時 2025-05-30 22:47:58
合計ジャッジ時間 57,526 ms
ジャッジサーバーID
(参考情報)
judge2 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 46
権限があれば一括ダウンロードができます

ソースコード

diff #

from __future__ import annotations
input


class CombLUT:
   MOD = 998_244_353

   _max = 0

   F = [1]
   InvF = [1]
   _fibo = [0, 1]
   _lucas = [2, 1]

   @classmethod
   def expand(cls, n):
      if n <= cls._max: return
      n = n*4//3
      cls.F.extend([1]*(n - cls._max))
      for i in range(cls._max + 1, n+1):
         cls.F[i] = cls.F[i-1] * i % cls.MOD
      cls.InvF.extend([1]*(n - cls._max))
      cls.InvF[n] = pow(cls.F[n], -1, cls.MOD)
      for i in range(n-1, cls._max, -1):
         cls.InvF[i] = cls.InvF[i+1] * (i+1) % cls.MOD
      cls._max = n

   @classmethod
   def comb(cls, n, r):
      if not (0 <= r <= n):
         return 0
      if n > cls._max: cls.expand(n)
      return cls.F[n] * cls.InvF[r] % cls.MOD * cls.InvF[n-r] % cls.MOD

   @classmethod
   def hyper_comb(cls, n, r):
      if (r < 0): return 0
      if (n < 0): return 0
      if n == r == 0: return 1
      if not (0 <= r <= n-1+r):
         return 0
      return cls.comb(n-1+r, r)

   @classmethod
   def neg_hyper_comb(cls, n, r):
      if (r < 0): return 0
      if n >= 0: return cls.hyper_comb(n, r)
      sgn = -1 if r&1 else 1
      return sgn * cls.comb(-n, r)

   @classmethod
   def factorial(cls, n):
      assert 0 <= n
      if n > cls._max: cls.expand(n)
      return cls.F[n]

   @classmethod
   def inv_factorial(cls, n):
      assert 0 <= n
      if n > cls._max: cls.expand(n)
      return cls.InvF[n]


def subset_sum(A, *, func=None, initial=None):
   if (func is None):
      if initial is None: initial = 0
      N = len(A)
      dp = [initial] * (1<<N)
      for h in range(N):
         for S in range(1<<h):
            dp[S|(1<<h)] = dp[S] + A[h]
      return dp
   else:
      assert (initial is not None)
      N = len(A)
      dp = [initial] * (1<<N)
      for h in range(N):
         for S in range(1<<h):
            dp[S|(1<<h)] = func(dp[S], A[h])
      return dp


class Convolution:
   """
    A class to perform convolution using the Fast Fourier Transform (FFT) algorithm.

    Attributes:
        _mod (int): A prime modulus used for modular arithmetic. Defaults to 998244353.
        _rank2 (int): The highest power of 2 dividing (mod - 1).
        _root (int): A primitive root of the modulus.
        _imag (int): Imaginary unit under the modulus.
        _iimag (int): Inverse of the imaginary unit under the modulus.
        _rate2 (tuple[int]): Precomputed powers of the primitive root, used for the FFT.
        _irate2 (tuple[int]): Precomputed inverse powers of the primitive root.
        _rate3 (tuple[int]): Precomputed powers of the primitive root for 3rd roots of unity.
        _irate3 (tuple[int]): Precomputed inverse powers for 3rd roots of unity.

    Note:
        This class uses a fixed modulus (998244353) by default. The modulus can be changed
        using the set_mod method, but be aware that changing the modulus can result in a
        significant performance drop on pypy. This is because, for the default modulus,
        division operations are optimized as constant divisions on pypy, but for custom
        moduli, these optimizations are not applied.
    """
   _mod = 998244353
   _rank2 = 23
   _root = 3
   _imag = 911660635
   _iimag = 86583718
   _rate2 = (
      911660635, 509520358, 369330050, 332049552, 983190778, 123842337, 238493703, 975955924, 603855026, 856644456,
      131300601, 842657263, 730768835, 942482514, 806263778, 151565301, 510815449, 503497456, 743006876, 741047443,
      56250497, 867605899
   )
   _irate2 = (
      86583718, 372528824, 373294451, 645684063, 112220581, 692852209, 155456985, 797128860, 90816748, 860285882,
      927414960, 354738543, 109331171, 293255632, 535113200, 308540755, 121186627, 608385704, 438932459, 359477183,
      824071951, 103369235
   )
   _rate3 = (
      372528824, 337190230, 454590761, 816400692, 578227951, 180142363, 83780245, 6597683, 70046822, 623238099,
      183021267, 402682409, 631680428, 344509872, 689220186, 365017329, 774342554, 729444058, 102986190, 128751033,
      395565204
   )
   _irate3 = (
      509520358, 929031873, 170256584, 839780419, 282974284, 395914482, 444904435, 72135471, 638914820, 66769500,
      771127074, 985925487, 262319669, 262341272, 625870173, 768022760, 859816005, 914661783, 430819711, 272774365,
      530924681
   )

   @classmethod
   def set_mod(cls, mod: int) -> None:
      """
        Sets a new modulus and recalculates the associated parameters.

        Args:
            mod (int): The new prime modulus.
        """
      cls._mod = mod
      cls._root = PrimeFactor.primitive_root(mod)
      cls._rank2 = tzcount(mod-1)
      root = [0]*(cls._rank2 + 1)
      iroot = [0]*(cls._rank2 + 1)
      root[cls._rank2] = pow(cls._root, (mod-1)>>cls._rank2, mod)
      iroot[cls._rank2] = pow(root[cls._rank2], mod-2, mod)
      for i in range(cls._rank2 - 1, -1, -1):
         root[i] = root[i+1] * root[i+1] % mod
         iroot[i] = iroot[i+1] * iroot[i+1] % mod
      cls._imag = root[2]
      cls._iimag = iroot[2]
      cls._rate2, cls._irate2 = cls.__calculate_rates(root, iroot, 2)
      cls._rate3, cls._irate3 = cls.__calculate_rates(root, iroot, 3)

   @classmethod
   def __calculate_rates(cls, root: list, iroot: list, ofs: int) -> tuple:
      """
        Calculates the rates used in the butterfly transformations.

        Args:
            root (list): List of roots.
            iroot (list): List of inverse roots.
            ofs (int): Offset to start calculation.

        Returns:
            tuple: A tuple containing two lists: rates and inverse rates.
        """
      rate = [0]*max(0, cls._rank2 - (ofs-1))
      irate = [0]*max(0, cls._rank2 - (ofs-1))
      prod, iprod = 1, 1
      for i in range(cls._rank2 - (ofs-1)):
         rate[i] = root[i + ofs] * prod % cls._mod
         irate[i] = iroot[i + ofs] * iprod % cls._mod
         prod *= iroot[i + ofs]
         prod %= cls._mod
         iprod *= root[i + ofs]
         iprod %= cls._mod
      return rate, irate

   @classmethod
   def butterfly(cls, a: list[int]) -> None:
      """
        Applies the butterfly transformation on the input list.

        Args:
            a (list[int]): The input list.
        """
      n = len(a)
      h = (n-1).bit_length()
      for len_ in range(0, h-1, 2):
         p = 1<<(h - len_ - 2)
         rot = 1
         for s in range(1<<len_):
            rot2 = rot*rot%cls._mod
            rot3 = rot2*rot%cls._mod
            offset = s<<(h - len_)
            for i in range(p):
               a0 = a[i + offset]
               a1 = a[i + offset + p] * rot % cls._mod
               a2 = a[i + offset + p*2] * rot2 % cls._mod
               a3 = a[i + offset + p*3] * rot3 % cls._mod
               a1na3imag = (a1-a3) * cls._imag % cls._mod
               a[i + offset] = (a0+a2+a1+a3) % cls._mod
               a[i + offset + p] = (a0+a2-a1-a3) % cls._mod
               a[i + offset + p*2] = (a0-a2 + a1na3imag) % cls._mod
               a[i + offset + p*3] = (a0-a2 - a1na3imag) % cls._mod
            if s+1 != 1<<len_:
               rot *= cls._rate3[(~s& -~s).bit_length() - 1]
               rot %= cls._mod
      if h&1:
         rot = 1
         for s in range(1<<(h-1)):
            offset = s<<1
            l = a[offset]
            r = a[offset + 1] * rot % cls._mod
            a[offset] = (l+r) % cls._mod
            a[offset + 1] = (l-r) % cls._mod
            if s+1 != 1<<(h-1):
               rot *= cls._rate2[(~s& -~s).bit_length() - 1]
               rot %= cls._mod

   @classmethod
   def butterfly_inv(cls, a: list[int]) -> None:
      """
        Applies the inverse butterfly transformation on the input list.

        Args:
            a (list[int]): The input list.
        """
      n = len(a)
      h = (n-1).bit_length()

      for len_ in range(h, 1, -2):
         p = 1<<(h - len_)
         irot = 1
         for s in range(1<<(len_-2)):
            irot2 = irot*irot%cls._mod
            irot3 = irot2*irot%cls._mod
            offset = s<<(h - len_ + 2)
            for i in range(p):
               a0 = a[i + offset]
               a1 = a[i + offset + p]
               a2 = a[i + offset + p*2]
               a3 = a[i + offset + p*3]
               a2na3iimag = (a2-a3) * cls._iimag % cls._mod
               a[i + offset] = (a0+a1+a2+a3) % cls._mod
               a[i + offset + p] = (a0-a1 + a2na3iimag) * irot % cls._mod
               a[i + offset + p*2] = (a0+a1-a2-a3) * irot2 % cls._mod
               a[i + offset + p*3] = (a0-a1 - a2na3iimag) * irot3 % cls._mod
            if s+1 != (1<<(len_-2)):
               irot *= cls._irate3[(~s& -~s).bit_length() - 1]
               irot %= cls._mod
      if h&1:
         p = 1<<(h-1)
         for i in range(p):
            l = a[i]
            r = a[i+p]
            a[i] = (l+r) % cls._mod
            a[i+p] = (l-r) % cls._mod

   @classmethod
   def convolution(cls, a: list[int], b: list[int]) -> list[int]:
      """
        Computes the convolution of two lists.

        Args:
            a (list[int]): First input list.
            b (list[int]): Second input list.

        Returns:
            list[int]: The convolution of a and b.

        Raises:
            ValueError: If the length of the result exceeds the supported length.
        """
      n, m = len(a), len(b)
      if n+m-1 > (1<<cls._rank2):
         raise ValueError('rank2 of given mod is too small.')
      if not n or not m: return []
      z = 1<<(n+m-2).bit_length()
      a = a + [0] * (z-n)
      b = b + [0] * (z-m)
      cls.butterfly(a)
      cls.butterfly(b)
      for i in range(z):
         a[i] *= b[i]
         a[i] %= cls._mod
      cls.butterfly_inv(a)
      a = a[:n+m-1]
      iz = pow(z, -1, cls._mod)
      for i in range(n+m-1):
         a[i] *= iz
         a[i] %= cls._mod
      return a


def dummy_frac(MOD=998_244_353, U=10**6):
   dp = [0, 1]
   dp += [0]*(U+1 - len(dp))
   for x in range(2, U+1):
      q, r = divmod(MOD, x)
      if dp[r] == 0:
         dp[x] = pow(x, -1, MOD)
      else:
         dp[x] = -(q) * dp[r] % MOD
   memo = {}

   def F(a=0, b=1):
      if not 1 <= b <= U: b %= MOD
      if b == 0: raise ZeroDivisionError
      if b == 1: return a
      if 1 <= b <= U:
         return a * dp[b] % MOD
      inv = memo.get(b)
      if inv is None:
         memo[b] = inv = pow(b, -1, MOD)
      return a*inv%MOD

   return F


Fraction = dummy_frac()


class ExpPoly:
   def __init__(self, lamda, coef: list[Fraction]):
      self.lamda = lamda
      self.coef = coef

   def __add__(self, other):
      raise NotImplementedError

   def __mul__(self, other: "int|Fraction|ExpPoly"):
      if isinstance(other, int):
         return ExpPoly(self.lamda, [c*other for c in self.coef])
      else:
         assert isinstance(other, ExpPoly)
         nshift = self.lamda + other.lamda
         # ncoef = convolution_naive(self.coef, other.coef, MOD=998_244_353)   # type: ignore
         ncoef = Convolution.convolution(self.coef, other.coef)
         return ExpPoly(nshift, ncoef)

   def __rmul__(self, other: "int|Fraction"):
      return self.__mul__(other)

   def integral(self):
      res = Fraction(0)
      pows = powers(pow(self.lamda, -1, MOD), len(self.coef) + 10, MOD=998_244_353)
      for n in range(len(self.coef)):
         c = self.coef[n]
         # res += c * CombLUT.factorial(n) % MOD * pow(self.lamda, -(n+1), MOD) % MOD
         res += c * CombLUT.factorial(n) % MOD * pows[n+1] % MOD
         res %= MOD
      return res


def powers(base, maxexp: int|float, MOD: int|None = None, *, negative: bool = False):
   maxexp = int(maxexp)
   if maxexp < 0: maxexp = 0
   if MOD is None:
      return [pow(base, exp) for exp in range(maxexp + 1)]
   else:
      base %= MOD
      res = [1%MOD] * (maxexp + 1)
      res[1] = base
      for exp in range(2, maxexp + 1):
         res[exp] = res[exp-1] * base % MOD
      return res


def bit_count(x):

   x = x - ((x>>1)&0x5555_5555_5555_5555)

   x = (x&0x3333_3333_3333_3333) + ((x>>2)&0x3333_3333_3333_3333)

   x = (x + (x>>4))&0x0f0f_0f0f_0f0f_0f0f
   x += (x>>8)
   x += (x>>16)
   x += (x>>32)
   return x&0x0000_0000_0000_007f


def solve(N, K, A):
   def resolve(k, a):
      lamda = Fraction(1, a)
      coef = [Fraction(0)] * k
      pows = powers(lamda, k+10, MOD=998_244_353)
      for n in range(k):
         # coef[n] = pow(lamda, n, MOD) * CombLUT.inv_factorial(n)
         coef[n] = pows[n] * CombLUT.inv_factorial(n) % MOD
      return ExpPoly(lamda, coef)

   F = [resolve(k, a) for k, a in zip(K, A)]

   dp = subset_sum(F, func=lambda x, y: x*y, initial=1)

   I = [f.integral() if isinstance(f, ExpPoly) else 0 for f in dp]

   popcnt = [Fraction(0)] * (N+1)
   for S in range(1<<N):
      cnt = bit_count(S)
      popcnt[cnt] += I[S]

   res = [Fraction(0)] * (N+1)
   for k in range(1, N+1):
      for i in range(k, N+1):
         h = CombLUT.hyper_comb(k+1, i-k)
         h *= (-1)**(i-k)
         res[k] += h * popcnt[i]
         res[k] %= MOD
   return res


MOD = 998_244_353

N = int(input())
K, A = [], []
for _ in range(N):
   k, a = map(int, input().split())
   K.append(k)
   A.append(a)

ans = solve(N, K, A)
ans.pop(0)
ans.reverse()

from itertools import accumulate

ans = list(accumulate(ans))
ans = [x%MOD for x in ans]

print(*ans)
0