103226: [Atcoder]ABC322 G - Two Kinds of Base
Description
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
Input
Output
分数:$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=(S_1,S_2,\dots,S_k)$和正整数$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)$。
样例输入 2
9 30
样例输出 2
31
样例输入 3
322322322 200000
样例输出 3
140058961