結果

問題 No.1693 Invasion
ユーザー ogami
提出日時 2021-10-01 22:08:24
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 248 ms / 2,000 ms
コード長 1,928 bytes
コンパイル時間 356 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 82,432 KB
最終ジャッジ日時 2024-07-19 11:28:19
合計ジャッジ時間 3,530 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil,pi,factorial,gcd,atan,degrees,sqrt
    from operator import itemgetter
    def I(): return int(input())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))
    def SI(): return input().rstrip()
    def printns(x): print('\n'.join(x))
    def printni(x): print('\n'.join(list(map(str,x))))
    def myceil(a,b):
        return (-(-a//b))
    inf = 10**17
    mod = 10**9 + 7
    mod =998244353

    n,m = MI()
    lis = LI()
    lis = list(set(lis))
    N = len(lis)
    dist = [inf]*(m+1)
    dist[0] = 0
    Q = deque([0])
    while Q:
        x = Q.popleft()
        for i in range(N):
            nex = x + lis[i]
            if nex<=m and dist[nex]==inf:
                dist[nex] = dist[x] + 1
                Q.append(nex)
    #print(dist)
    ans = 0
    def table(max_size,mod):
        fact = [1]*(max_size+1)
        invfact = [1]*(max_size+1)
        for i in range(1,max_size+1):
            fact[i] = i*fact[i-1]%mod
        invfact[max_size] = pow(fact[max_size],mod-2,mod)
        for i in range(max_size,0,-1):
            invfact[i-1] = invfact[i]*(i)%mod
        return fact,invfact

    fact,invfact = table(200000,mod)
    def comb(n,r,mod):
        return fact[n]*invfact[n-r]*invfact[r]%mod
    for i in range(m+1):
        dis = dist[i]
        rest = i-dis
        if dis!=inf:
            ans += comb(m-dis,rest,mod)
            ans %= mod
    print(ans)

        
if __name__=="__main__":
    main()
0