提出 #71705392

---

ソースコード 拡げる

import sys
import string
import math
import bisect
import os
import heapq
import operator
from io import BytesIO, IOBase
from heapq import heappop,heappush
from functools import lru_cache,cache
from collections import deque,defaultdict,Counter,OrderedDict
from itertools import permutations,combinations
from array import array

INF = float('inf')
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0
 
    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
 
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
 
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
 
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = sys.stdin.buffer.readline

ask = lambda *x:print('?',*x,flush=True)
reply = lambda *x:print('!',*x,flush=True)

RI = lambda: int(sys.stdin.readline())
RF = lambda: float(sys.stdin.readline())
RS = lambda: sys.stdin.readline().strip()
RFF = lambda: map(float, sys.stdin.readline().split())
RII = lambda: map(int, sys.stdin.readline().split())
RSS = lambda: map(str, sys.stdin.readline().strip().split())
RIL = lambda: list(RII())
RFL = lambda: list(RFF())
RSL = lambda: list(RSS())

from types import GeneratorType
def bootstrap(f, stack=[]):
    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break 
                    to = stack[-1].send(to)
            return to

    return wrappedfunc

class NTT:
    def __init__(self, mod=998244353, g=3):
        self.mod = mod
        self.g = g
        self.roots = [0, 1]
        self.inv_roots = [0, 1]
        self._prepare_roots(20)
    
    def _prepare_roots(self, n):
        while len(self.roots) <= n:
            k = len(self.roots)
            root = pow(self.g, (self.mod - 1) // (1 << k), self.mod)
            inv_root = pow(root, self.mod - 2, self.mod)
            self.roots.append(root)
            self.inv_roots.append(inv_root)
    
    def _ntt(self, a, invert=False):
        n = len(a)
        if n == 1:
            return

        j = 0
        for i in range(1, n):
            bit = n >> 1
            while j & bit:
                j ^= bit
                bit >>= 1
            j ^= bit
            if i < j:
                a[i], a[j] = a[j], a[i]
                
        length = 2
        while length <= n:
            k = length.bit_length() - 1
            if k >= len(self.roots):
                self._prepare_roots(k)
            
            root = self.roots[k] if not invert else self.inv_roots[k]
            
            for i in range(0, n, length):
                w = 1
                for j in range(i, i + length // 2):
                    u = a[j]
                    v = a[j + length // 2] * w % self.mod
                    a[j] = (u + v) % self.mod
                    a[j + length // 2] = (u - v) % self.mod
                    w = w * root % self.mod
            
            length <<= 1
        
        if invert:
            inv_n = pow(n, self.mod - 2, self.mod)
            for i in range(n):
                a[i] = a[i] * inv_n % self.mod
    
    def next_power_of_two(self, n):
        if n <= 1:
            return 1
        return 1 << (n - 1).bit_length()
    
    def poly_multiply(self, a, b):
        if not a or not b:
            return []
        
        n = self.next_power_of_two(len(a) + len(b) - 1)
        
        fa = a + [0] * (n - len(a))
        fb = b + [0] * (n - len(b))
        
        self._ntt(fa, False)
        self._ntt(fb, False)
        
        fc = [fa[i] * fb[i] % self.mod for i in range(n)]
        
        self._ntt(fc, True)
        
        result_len = len(a) + len(b) - 1
        return fc[:result_len]
    
    def convolution(self, a, b):
        return self.poly_multiply(a, b)

    def bostan_mori(self, P, Q, k):
        """
        Bostan-Mori算法计算 [x^k] P(x)/Q(x)
        
        参数:
            P: 分子多项式系数列表，从低次项开始 [c0, c1, ..., cn]
            Q: 分母多项式系数列表，从低次项开始 [c0, c1, ..., cm]
            k: 需要计算的系数次数
        
        返回:
            系数值
        """
        MOD = self.mod
        
        max_len = max(len(P), len(Q))
        P = P + [0] * (max_len - len(P))
        Q = Q + [0] * (max_len - len(Q))
        
        P = [x % MOD for x in P]
        Q = [x % MOD for x in Q]
        
        while k > 0:
            Q_minus = [q * (1 if i % 2 == 0 else MOD-1) % MOD for i, q in enumerate(Q)]
            
            V = self.convolution(Q, Q_minus)
            U = self.convolution(P, Q_minus)
            
            if k % 2 == 0:
                P = [U[i] for i in range(0, len(U), 2)]
            else:
                P = [U[i] for i in range(1, len(U), 2)]
            
            Q = [V[i] for i in range(0, len(V), 2)]
            
            k //= 2
        
        return (P[0] * pow(Q[0],-1,MOD)) % MOD

def main():
    n,m = RII()
    a = RIL()
    a.append(1)
    n += 1
    a.sort()
    
    MOD = 998244353
    
    Q = [0]*(10010)
    Q[0] = 1
    for x in a:
        for i in range(10009,-1,-1):
            if Q[i]>0:
                Q[i+x] = (Q[i+x]-Q[i])%MOD
    
    P = [0]*(10010)
    P[0] = 1
    
    #print(P,Q)
    
    ntt = NTT()
    ans = ntt.bostan_mori(P,Q,m)
    
    print(ans)
    
    
        
        
        
        

if __name__ == '__main__':
    main()

提出情報

ジャッジ結果