atcoder#ABC279G. [ABC279G] At Most 2 Colors

[ABC279G] At Most 2 Colors

题目描述

1 × N 1\ \times\ N のマス目があり、マスには左から 1,2,,N 1,2,\dots,N の番号が付いています。

高橋君は C C 色の絵の具を用意し、各マスを C C 色のいずれかで塗りました。
すると、どの連続する K K マスを見ても高々 2 2 色しか現れませんでした。
厳密には、 1  i  NK+1 1\ \le\ i\ \le\ N-K+1 を満たす全ての整数 i i について、マス i,i+1,,i+K1 i,i+1,\dots,i+K-1 には高々 2 2 色しか現れませんでした。

高橋君の色の塗り方として考えられるものは何通りですか?
この数は非常に大きくなる場合があるので、 998244353 998244353 で割った余りを求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

N N K K C C

输出格式

答えを整数として出力せよ。

题目大意

现在有一个 1×N 1\times N 的格子和 C C 种颜色。

每一个格子上都涂了这 C C 种颜色的其中一种,并且任意相邻的 K K 个格子最多有两种不同的颜色。

准确地说,对于每一个 i(1iNK+1) i(1\le i\le N-K+1) ,格子 i,i+1,,i+K1 i,i+1,\cdots,i+K-1 中,最多存在两种不同颜色。

求出有多少种方案给这些格子染色,对 998244353 998244353 取模。

3 3 3
21
10 5 2
1024
998 244 353
952364159

提示

制約

  • 入力は全て整数
  • 2  K  N  106 2\ \le\ K\ \le\ N\ \le\ 10^6
  • 1  C  109 1\ \le\ C\ \le\ 10^9

Sample Explanation 1

この入力では、マス目は 1 × 3 1\ \times\ 3 です。 連続する 3 3 マスの中で高々 2 2 色しか現れないように塗る方法は、考えうる全ての塗り方 27 27 通りから全てのマスを異なる色で塗る 6 6 通りを引いた 21 21 通りです。

Sample Explanation 2

C=2 C=2 なので、どのように塗っても連続する K K マスには高々 2 2 色しか含まれません。

Sample Explanation 3

998244353 998244353 で割った余りを出力してください。