atcoder#ABC279G. [ABC279G] At Most 2 Colors
[ABC279G] At Most 2 Colors
题目描述
のマス目があり、マスには左から の番号が付いています。
高橋君は 色の絵の具を用意し、各マスを 色のいずれかで塗りました。
すると、どの連続する マスを見ても高々 色しか現れませんでした。
厳密には、 を満たす全ての整数 について、マス には高々 色しか現れませんでした。
高橋君の色の塗り方として考えられるものは何通りですか?
この数は非常に大きくなる場合があるので、 で割った余りを求めてください。
输入格式
入力は以下の形式で標準入力から与えられる。
输出格式
答えを整数として出力せよ。
题目大意
现在有一个 的格子和 种颜色。
每一个格子上都涂了这 种颜色的其中一种,并且任意相邻的 个格子最多有两种不同的颜色。
准确地说,对于每一个 ,格子 中,最多存在两种不同颜色。
求出有多少种方案给这些格子染色,对 取模。
3 3 3
21
10 5 2
1024
998 244 353
952364159
提示
制約
- 入力は全て整数
Sample Explanation 1
この入力では、マス目は です。 連続する マスの中で高々 色しか現れないように塗る方法は、考えうる全ての塗り方 通りから全てのマスを異なる色で塗る 通りを引いた 通りです。
Sample Explanation 2
なので、どのように塗っても連続する マスには高々 色しか含まれません。
Sample Explanation 3
で割った余りを出力してください。