102422: [AtCoder]ABC242 C - 1111gal password
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Score : $300$ points
Problem Statement
Given an integer $N$, find the number of integers $X$ that satisfy all of the following conditions, modulo $998244353$.
- $X$ is an $N$-digit positive integer.
- Let $X_1,X_2,\dots,X_N$ be the digits of $X$ from top to bottom. They satisfy all of the following:
- $1 \le X_i \le 9$ for all integers $1 \le i \le N$;
- $|X_i-X_{i+1}| \le 1$ for all integers $1 \le i \le N-1$.
Constraints
- $N$ is an integer.
- $2 \le N \le 10^6$
Input
Input is given from Standard Input in the following format:
$N$
Output
Print the answer as an integer.
Sample Input 1
4
Sample Output 1
203
Some of the $4$-digit integers satisfying the conditions are $1111,1234,7878,6545$.
Sample Input 2
2
Sample Output 2
25
Sample Input 3
1000000
Sample Output 3
248860093
Be sure to find the count modulo $998244353$.
Input
题意翻译
给出整数 $N$，请求出长度为 $N$ 的满足以下条件的正整数 $X$ 的情况数，除以 $998244353$ 的余数。 1.$X$长度为 $N$。 2.若 $X$ 的各个数位表示为 $x_1,x_2,……x_n$，则它们满足以下条件： - 对于所有正整数 $i$（$1 \le\ i \le\ N$），$1 \le\ x_i \le\ 9$ - 对于所有正整数 $i$（$1 \le\ i < N$），$|x_{i+1}-x_i| \le\ 1$Output
分数：300分
问题描述
给定一个整数$N$，找出满足以下所有条件的整数$X$的数量，取模$998244353$。
- $X$是一个$N$位正整数。
- 将$X$的各位数字从上到下表示为$X_1,X_2,\dots,X_N$。它们满足以下所有条件：
- 对于所有整数$1 \le i \le N$，有$1 \le X_i \le 9$；
- 对于所有整数$1 \le i \le N-1$，有$|X_i-X_{i+1}| \le 1$。
约束
- $N$是一个整数。
- $2 \le N \le 10^6$
输入
输入格式如下：
$N$
输出
打印一个整数作为答案。
样例输入1
4
样例输出1
203
满足条件的$4$位整数有$1111,1234,7878,6545$等。
样例输入2
2
样例输出2
25
样例输入3
1000000
样例输出3
248860093
确保取模$998244353$得到的答案。