G - Yet Another RGB Sequence
Editorial
/
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
整数 R,G,B,K が与えられます。R
, G
, B
からなる文字列 S であって、以下の条件をすべて満たすものの個数を 998244353 で割った余りを求めてください。
- S に含まれる
R
,G
,B
の個数はそれぞれ R,G,B 個である。 - S に(連続する)部分文字列として含まれる
RG
の個数は K 個である。
制約
- 1 \leq R,G,B\leq 10^6
- 0 \leq K \leq \mathrm{min}(R,G)
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
R G B K
出力
答えを出力せよ。
入力例 1
2 1 1 1
出力例 1
6
条件を満たす文字列は以下の 6 個です。
RRGB
RGRB
RGBR
RBRG
BRRG
BRGR
入力例 2
1000000 1000000 1000000 1000000
出力例 2
80957240
個数を 998244353 で割った余りを求めてください。
Score : 600 points
Problem Statement
You are given integers R, G, B, and K. How many strings S consisting of R
, G
, and B
satisfy all of the conditions below? Find the count modulo 998244353.
- The number of occurrences of
R
,G
, andB
in S are R, G, and B, respectively. - The number of occurrences of
RG
as (contiguous) substrings in S is K.
Constraints
- 1 \leq R,G,B\leq 10^6
- 0 \leq K \leq \mathrm{min}(R,G)
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
R G B K
Output
Print the answer.
Sample Input 1
2 1 1 1
Sample Output 1
6
The following six strings satisfy the conditions.
RRGB
RGRB
RGBR
RBRG
BRRG
BRGR
Sample Input 2
1000000 1000000 1000000 1000000
Sample Output 2
80957240
Find the count modulo 998244353.