/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
非負整数列 S=(S_1,S_2,\dots,S_k) と整数 a に対して、以下のように関数 f(S,a) を定義します。
- f(S,a) = \sum_{i=1}^{k} S_i \times a^{k - i}
例えば、f((1,2,3),4) = 1 \times 4^2 + 2 \times 4^1 + 3 \times 4^0 = 27,f((1,1,1,1),10) = 1 \times 10^3 + 1 \times 10^2 + 1 \times 10^1 + 1 \times 10^0 = 1111 です。
正整数 N,X が与えられます。以下の条件を全て満たす非負整数列 S=(S_1,S_2,\dots,S_k) と正整数 a,b の組 (S,a,b) の個数を 998244353 で割ったあまりを求めてください。
- k \ge 1
- a,b \le N
- S_1 \neq 0
- S_i < \min(10,a,b)(1 \le i \le k)
- f(S,a) - f(S,b) = X
制約
- 1 \le N \le 10^9
- 1 \le X \le 2 \times 10^5
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N X
出力
条件を満たす非負整数列 S と正整数 a,b の組 (S,a,b) の個数を 998244353 で割ったあまりを出力せよ。
入力例 1
4 2
出力例 1
5
(S,a,b)=((1,0),4,2),((1,1),4,2),((2,0),4,3),((2,1),4,3),((2,2),4,3) の 5 通りが条件を満たします。
入力例 2
9 30
出力例 2
31
入力例 3
322322322 200000
出力例 3
140058961
Score : 600 points
Problem Statement
For a non-negative integer sequence S=(S_1,S_2,\dots,S_k) and an integer a, we define the function f(S,a) as follows:
- f(S,a) = \sum_{i=1}^{k} S_i \times a^{k - i}.
For example, f((1,2,3),4) = 1 \times 4^2 + 2 \times 4^1 + 3 \times 4^0 = 27, and f((1,1,1,1),10) = 1 \times 10^3 + 1 \times 10^2 + 1 \times 10^1 + 1 \times 10^0 = 1111.
You are given positive integers N and X. Find the number, modulo 998244353, of triples (S,a,b) of a sequence of non-negative integers S=(S_1,S_2,\dots,S_k) and positive integers a and b that satisfy all of the following conditions.
- k \ge 1
- a,b \le N
- S_1 \neq 0
- S_i < \min(10,a,b)(1 \le i \le k)
- f(S,a) - f(S,b) = X
Constraints
- 1 \le N \le 10^9
- 1 \le X \le 2 \times 10^5
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N X
Output
Print the number, modulo 998244353, of triples (S,a,b) of a sequence of non-negative integers S=(S_1,S_2,\dots,S_k) and positive integers a and b that satisfy the conditions.
Sample Input 1
4 2
Sample Output 1
5
The five triples (S,a,b)=((1,0),4,2),((1,1),4,2),((2,0),4,3),((2,1),4,3),((2,2),4,3) satisfy the conditions.
Sample Input 2
9 30
Sample Output 2
31
Sample Input 3
322322322 200000
Sample Output 3
140058961