結果

問題 No.1693 Invasion
ユーザー ogamiogami
提出日時 2021-10-01 22:08:24
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 300 ms / 2,000 ms
コード長 1,928 bytes
コンパイル時間 390 ms
コンパイル使用メモリ 86,832 KB
実行使用メモリ 83,276 KB
最終ジャッジ日時 2023-09-26 17:29:45
合計ジャッジ時間 5,255 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 112 ms
79,464 KB
testcase_01 AC 114 ms
79,468 KB
testcase_02 AC 123 ms
79,188 KB
testcase_03 AC 118 ms
79,988 KB
testcase_04 AC 115 ms
79,596 KB
testcase_05 AC 117 ms
79,596 KB
testcase_06 AC 117 ms
79,860 KB
testcase_07 AC 117 ms
80,544 KB
testcase_08 AC 119 ms
80,628 KB
testcase_09 AC 231 ms
82,820 KB
testcase_10 AC 157 ms
81,676 KB
testcase_11 AC 144 ms
80,956 KB
testcase_12 AC 158 ms
82,020 KB
testcase_13 AC 139 ms
80,928 KB
testcase_14 AC 158 ms
81,212 KB
testcase_15 AC 152 ms
81,148 KB
testcase_16 AC 197 ms
81,864 KB
testcase_17 AC 115 ms
79,572 KB
testcase_18 AC 287 ms
83,232 KB
testcase_19 AC 116 ms
80,592 KB
testcase_20 AC 117 ms
79,568 KB
testcase_21 AC 294 ms
83,012 KB
testcase_22 AC 202 ms
82,480 KB
testcase_23 AC 300 ms
83,276 KB
権限があれば一括ダウンロードができます

ソースコード

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