/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 600 点
問題文
長さ N の正整数列 A=(A _ 1,A _ 2,\ldots,A _ N) および正整数 M が与えられます。
次の条件を満たす長さ N の非負整数列 x=(x _ 1,x _ 2,\ldots,x _ N) がいくつあるか求めてください。
- \displaystyle\sum _ {i=1} ^ NA _ ix _ i\le M
答えは非常に大きくなる場合があるので、答えを 998244353 で割った余りを求めてください。
制約
- 1\le N\le100
- 1\le A _ i\le100\ (1\le i\le N)
- 1\le M\le10 ^ {18}
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M A _ 1 A _ 2 \ldots A _ N
出力
条件を満たす非負整数列の個数を 998244353 で割った余りを出力せよ。
入力例 1
4 6 5 4 3 2
出力例 1
10
条件を満たす x は (0,0,0,0),(0,0,0,1),(0,0,0,2),(0,0,0,3),(0,0,1,0),(0,0,1,1),(0,0,2,0),(0,1,0,0),(0,1,0,1),(1,0,0,0) の 10 個です。
よって、10 を出力してください。
入力例 2
6 89 4 7 5 10 7 6
出力例 2
38469
入力例 3
1 1000000007 1
出力例 3
1755655
条件を満たす x は 1000000008 個あります。
これを 998244353 で割った余りである 1755655 を出力してください。
入力例 4
20 738894495848985641 40 58 13 24 65 11 63 29 98 75 40 77 15 50 83 85 35 46 38 37
出力例 4
31156940
Score : 600 points
Problem Statement
You are given a length-N sequence of positive integers A=(A _ 1,A _ 2,\ldots,A _ N) and a positive integer M.
Find the number of length-N sequences of non-negative integers x=(x _ 1,x _ 2,\ldots,x _ N) that satisfy the following condition:
- \displaystyle\sum _ {i=1} ^ NA _ ix _ i\le M
The number can be very large, so find it modulo 998244353.
Constraints
- 1\le N\le100
- 1\le A _ i\le100\ (1\le i\le N)
- 1\le M\le10 ^ {18}
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M A _ 1 A _ 2 \ldots A _ N
Output
Print the number, modulo 998244353, of non-negative integer sequences that satisfy the condition.
Sample Input 1
4 6 5 4 3 2
Sample Output 1
10
The sequences x that satisfy the condition are the following 10: (0,0,0,0),(0,0,0,1),(0,0,0,2),(0,0,0,3),(0,0,1,0),(0,0,1,1),(0,0,2,0),(0,1,0,0),(0,1,0,1),(1,0,0,0).
Thus, print 10.
Sample Input 2
6 89 4 7 5 10 7 6
Sample Output 2
38469
Sample Input 3
1 1000000007 1
Sample Output 3
1755655
There are 1000000008 sequences x that satisfy the condition.
Print this modulo 998244353, which is 1755655.
Sample Input 4
20 738894495848985641 40 58 13 24 65 11 63 29 98 75 40 77 15 50 83 85 35 46 38 37
Sample Output 4
31156940