4265: 1111gal password

内存限制:128 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:0 解决:0

题目描述

# 1111gal password ### 内存 1024MB ### 时间 2S ## 题目描述 给定一个整数 $N$,请计算满足以下所有条件的整数 $X$ 的数量,结果对 998244353 取模。 - $X$ 是一个 $N$ 位正整数。 - 设 $X_1,X_2,...,X_N$ 为 $X$ 从高位到低位的各个数字。它们满足以下所有条件: - 对于所有整数$1 ≤ i ≤ N$,有$1 ≤ X_i ≤ 9$; - 对于所有整数$1 ≤ i ≤ N-1$,有$|X_i-X_{i+1}| ≤ 1$。 ## 输入格式 输入$N$。 ## 输出格式 输出所求答案。 ## 输入输出样例 ### 输入样例1 ``` 4 ``` ### 输出样例1 ``` 203 ``` ### 输入样例2 ``` 2 ``` ### 输出样例2 ``` 25 ``` ### 输入样例3 ``` 1000000 ``` ### 输出样例3 ``` 248860093 ``` ## 数据范围与提示 【样例1说明】 满足条件的4位整数包括 1111,1234,7878,6545 等。 【样例3说明】 请注意结果对998244353取模。 【数据范围】 $N$ 是整数,$2 ≤ N ≤ 10^6$。 ## 题目来源 ABC242C