← 返回题目列表

Codeforces · 1938/D

D. 班博

中文机器翻译题面 查看原题

以下页面来自赛事官方发布的原题PDF,已完整保存并渲染到本地。

Bánh Bò - 原题 PDF 第 1 页
原题PDF第7页
Bánh Bò - 原题 PDF 第 2 页
原题PDF第8页
可复制的 PDF 提取文本
Problem D
                         B´anh B`o
                    Time limit: 15 seconds


Ever since the Earth got destroyed, Trillian has been missing some Earth delicacies. Today, she had the spaceship’s
food machine generate for her a Vietnamese delicacy she once enjoyed: bánh bò hấp (steamed chewy sponge cake).

Trillian has an unlimited number of bánh bò hấp pieces. Each piece of bánh bò hấp is either red or white. She wants
to assemble rc pieces of bánh bò hấp into a grid with dimensions r × c, where each cell contains a single piece of
bánh bò hấp. Thus, there are exactly 2rc distinct ways to assemble bánh bò hấp into an r × c grid, since we consider
pieces of the same color to be identical.

We say an assembly of bánh bò hấp is uniform if all 6×7 subgrids have the same number of red pieces. Consequently,
in a uniform bánh bò hấp assembly, all 6 × 7 subgrids have the same number of white pieces as well. Note that an
r × c grid has (r −5)(c −6) subgrids of dimensions 6 × 7.

For example, Figure D.1 illustrates a uniform assembly of 7 × 8 pieces of bánh bò hấp, where shaded cells represent
red bánh bò hấp pieces and unshaded cells represent white bánh bò hấp pieces. Figure D.2 shows that all four 6 × 7
subgrids have 6 red pieces and 36 white pieces.





                           Figure D.1: An example of uniform bánh bò hấp assembly.





        Figure D.2: All four 6 × 7 subgrids of the uniform bánh bò hấp assembly illustrated in Figure D.1.

Given r and c, where r is a multiple of 6 and c is a multiple of 7, Trillian would like to calculate the number of
possible uniform bánh bò hấp assemblies modulo 998 244 353.





ICPC Asia Pacific Championship 2024 Problem D: B´anh B`o

Input
Input consists of a single line containing two integers r and c (6 ≤r ≤66 666; r is a multiple of 6; 7 ≤c ≤77 777; c
is a multiple of 7).

Output

Output the number of possible uniform bánh bò hấp assemblies modulo 998 244 353.


 Sample Input #1                          Sample Output #1
 6 7                                    780136139



Explanation for the sample input/output #1
The output is 242 modulo 998 244 353.


 Sample Input #2                          Sample Output #2
 12 14                                  22889737



 Sample Input #3                          Sample Output #3
 12 42                                  96403614



 Sample Input #4                          Sample Output #4
 42 14                                  94940316





ICPC Asia Pacific Championship 2024 Problem D: B´anh B`o