結果

問題 No.1693 Invasion
ユーザー ogamiogami
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 59 ms
63,232 KB
testcase_01 AC 64 ms
63,360 KB
testcase_02 AC 64 ms
63,744 KB
testcase_03 AC 69 ms
66,048 KB
testcase_04 AC 61 ms
63,872 KB
testcase_05 AC 65 ms
66,304 KB
testcase_06 AC 67 ms
65,920 KB
testcase_07 AC 72 ms
67,328 KB
testcase_08 AC 67 ms
67,328 KB
testcase_09 AC 178 ms
81,280 KB
testcase_10 AC 120 ms
80,512 KB
testcase_11 AC 99 ms
79,744 KB
testcase_12 AC 108 ms
80,128 KB
testcase_13 AC 90 ms
75,776 KB
testcase_14 AC 113 ms
80,256 KB
testcase_15 AC 106 ms
79,616 KB
testcase_16 AC 145 ms
80,256 KB
testcase_17 AC 64 ms
63,360 KB
testcase_18 AC 212 ms
82,432 KB
testcase_19 AC 60 ms
65,408 KB
testcase_20 AC 63 ms
66,048 KB
testcase_21 AC 225 ms
82,048 KB
testcase_22 AC 147 ms
80,768 KB
testcase_23 AC 248 ms
82,176 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