Bánh Bò (Problem D, The 2024 ICPC Asia Pacific Championship, 2024)
Time limit: 15 sec
Author: Kevin Charles Atienza

# Problem Statement

*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 into a grid with dimensions $r \times c$, where each cell contains a single piece of bánh bò hấp. Thus, there are exactly $2^{rc}$ distinct ways to assemble bánh bò hấp into an $r \times 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 \times 7$ subgrids have the same number of red pieces. Consequently, in a uniform bánh bò hấp assembly, all $6 \times 7$ subgrids have the same number of white pieces as well. Note that an $r \times c$ grid has $(r - 5)(c - 6)$ subgrids of dimensions $6 \times 7$.

For example, Figure D.1 illustrates a uniform assembly of $7 \times 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 \times 7$ subgrids have 6 red pieces and 36 white pieces.

![Figure D.1](icpc-apac-2024-banh-1.png)

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

![Figure D.2](icpc-apac-2024-banh-2.png)

*Figure D.2: All four $6 \times 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.

# Input

Input consists of a single line containing two integers $r$ and $c$ ($6 \leq r \leq 66\ 666$; $r$ is a multiple of 6; $7 \leq c \leq 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
```
6 7
```
# Sample Output #1
```
780136139
```
*Explanation for the sample input/output #1*

The output is $2^{42}$ modulo 998 244 353.

# Sample Input #2
```
12 14
```
# Sample Output #2
```
22889737
```
# Sample Input #3
```
12 42
```
# Sample Output #3
```
96403614
```
# Sample Input #4
```
42 14
```
# Sample Output #4
```
94940316
```

Sample inputs:
6 7

12 14

12 42

42 14

Sample outputs:
780136139

22889737

96403614

94940316

# Solution Analysis
Analysis author: Kevin Charles Atienza, Mitsuru Kusumoto

Let $g_{i,j} \in \{0,1\}$ be the value at row $i$ and column $j$. We use zero-indexing ($0 \le i < r$ and $0 \le j < c$). Also, for simplicity sake, let $r_0 = 6$ and $c_0 = 7$.

### **Observation D.1** (“Quadrangle Equation”).  
*For* $r_0 \le i < r$ *and* $c_0 \le j < c$,  
$g_{i,j} + g_{i - r_0, j - c_0} = g_{i - r_0, j} + g_{i, j - c_0}$.

**Proof.** Consider a $(r_0 + 1) \times (c_0 + 1)$ grid. Its four $r_0 \times c_0$ subgrids overlap.  
Adding the top-left and the bottom-right subgrids and subtracting the bottom-left and the top-right subgrids will yield the equation. ∎

Observation D.1 has several nice consequences.  
For instance, in any $(r_0 + 1) \times (c_0 + 1)$ subgrid you can check that the only possibilities for the four corners are:
```
0 · · · 0
.       .
.       .
.       .
0 · · · 0
```
or
```
1 · · · 1
.       .
.       .
.       .
1 · · · 1
```
or
```
0 · · · 1
.       .
.       .
.       .
0 · · · 1
```
or
```
1 · · · 0
.       .
.       .
.       .
1 · · · 0
```
or
```
0 · · · 0
.       .
.       .
.       .
1 · · · 1
```
or
```
1 · · · 1
.       .
.       .
.       .
0 · · · 0
```

Since these six “tiles” can only be assembled in limited ways, we eventually observe that:

### **Observation D.2.**  

In the lattice $\{(i + r_0 a, j + c_0 b)\ |\ 0 \le a < r/r_0, 0 \le b < c/c_0\}$ for each $(i,j) \in \{0, \ldots, r_0 - 1\} \times \{0, \ldots, c_0 - 1\}$, at least one of the following holds:  (1) for each row, all cells in it contain the same bit, or (2) for each column, all cells in it contain the same bit.  (Both can be true.)

Observation D.1 also tells us that after we choose the topmost $r_0$ rows and leftmost $c_0$ columns, all the other cells are completely determined. Thus, all that remains is to choose the cells in those rows and columns while satisfying the following necessary conditions, which can also be shown to be sufficient by induction:

- For each $(i, j)$ such that $0 \le i < r_0$ and $0 \le j < c_0$, one (or both) of the following hold:  
  (A) $g_{i,j} = g_{i+r_0,j} = g_{i+2r_0,j} = g_{i+3r_0,j} = \ldots$  
  and/or  
  (B) $g_{i,j} = g_{i,j+c_0} = g_{i,j+2c_0} = g_{i,j+3c_0} = \ldots$

- $g_{i,0} + g_{i,1} + \ldots + g_{i,c_0-1} = g_{i+r_0,0} + g_{i+r_0,1} + \ldots + g_{i+r_0,c_0-1}$ for $0 \le i < r_0$ and $0 \le a < r/r_0$, and

- $g_{0,j} + g_{1,j} + \ldots + g_{r_0-1,j} = g_{0,j+c_0} + g_{1,j+c_0} + \ldots + g_{r_0-1,j+c_0}$ for $0 \le j < c_0$ and $0 \le b < c/c_0$.


For further clarity, let’s define a pair $(i,j)$ as being **constant** if the values of $g_{i+r_0 a,j+c_0 b}$ remain consistent for all $a$ and $b$. If condition (A) is satisfied for $(i,j)$, we denote the pair as being **horizontally striped**.  
Likewise, if condition (B) is met for $(i,j)$, we denote the pair as being **vertically striped**. Note that these conditions for $(i,j)$–being constant, being horizontally striped, and being vertically striped–are not mutually exclusive. For example, being horizontally striped can include the case of being constant.

For the top-left $r_0 \times c_0$ cells, let’s assume that each cell is fixed as one of constant, horizontally striped, or vertically striped. We will now determine the number of possible value assignments for the topmost $r_0$ rows and the leftmost $c_0$ columns. For simplicity, let $p = r/r_0 - 1$ and $q = c/c_0 - 1$. Let’s fix the values of $g_{i,j}$ to $x_{i,j} \in \{0, 1\}$ for $0 \le i < r_0$ and $0 \le j < c_0$. Let $H$ denote the set of horizontally striped cells and $V$ denote the set of vertically striped cells.

- The number of ways to fill the remaining cells in the leftmost $c_0$ columns is $\prod_{i=0}^{r_0-1} \binom{m_i}{n_i}^p$, where  
  $m_i = \#\{j\ |\ (i,j) \in H\}$ and $n_i = \#\{j\ |\ (i,j) \in H, x_{i,j} = 1\}$.

- The number of ways to fill the remaining cells in the topmost $r_0$ rows is $\prod_{j=0}^{c_0-1} \binom{m_j'}{n_j'}^q$, where  
  $m_j' = \#\{i\ |\ (i,j) \in V\}$ and $n_j' = \#\{i\ |\ (i,j) \in V, x_{i,j} = 1\}$.

By summing over all possible combinations of values for $x_{i,j}$, the number of ways to fill the topmost $r_0$ rows and the leftmost $c_0$ columns is  
$$
2^{r_0c_0 - |H| - |V|} \cdot \left( \prod_{i=0}^{r_0-1} \sum_{k=0}^{m_i} \binom{m_i}{k}^{p+1} \right) \cdot \left( \prod_{j=0}^{c_0-1} \sum_{k'=0}^{m_i'} \binom{m_i'}{k'}^{q+1} \right)
$$

Furthermore, if $(i,j)$ is vertically striped and it is not constant, we refer to the pair as **strictly vertically striped**.

When we fix that each of the top-left $r_0 \times c_0$ cells is either strictly vertically striped or horizontally striped, the number of ways to fill the cells can be represented as $\prod_{i=0}^{r_0-1} f(m_i) \cdot \prod_{j=0}^{c_0-1} f'(m_j')$ for some functions $f$ and $f'$, which can be obtained through a calculation of inclusion and exclusion. Here, with $H$ denoting a set of horizontally striped cells, we define $m_i = \#\{j\ |\ (i,j) \in H\}$ and $m_j' = \#\{i\ |\ (i,j) \in H\}$. Note that the two conditions, "strictly vertically striped" and "horizontally striped", are mutually exclusive and collectively exhaustive.

From this observation, you can compute the solution of this problem in several ways. One is dynamic programming: There are $2^{r_0 c_0}$ ways to fix "strictly vertically striped" or "horizontally striped" for each cell. Performing a brute-force search is too slow, but you can implement DP computation with some pruning tricks to improve efficiency.

Another approach is using generating functions:  
Suppose that column $j$ corresponds to a variable $z_j$ and that having $m_j'$ horizontally striped cells in column $j$ corresponds to $z_j^{m_j'}$. A polynomial for one row is represented as

$$
G = \sum_{x_0, x_1, \ldots, x_{c_0 - 1} \in \{0,1\}} f(c_0 - x_0 - x_1 - \ldots - x_{c_0 - 1}) z_0^{x_0} \cdots z_{c_0 - 1}^{x_{c_0 - 1}}.
$$

Computing $G^{r_0}$ using Fast Fourier Transform (FFT) can lead to computing the solution efficiently. The runtime is $O(N \log N)$, where $N = (r_0 + 1)^{c_0}$.

**(Acknowledgement: This analysis is partially based on insightful feedback from Yui Hosaka.)**


Special judge (C++ scorer):
/**
 * Default validator from https://github.com/Kattis/problemtools
 * Modified (as small as possible) to tcframe format by jonathanirvings.
 */

#include <fstream>
#include <iostream>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cmath>
#include <cstdarg>

std::ifstream judgein, judgeans, conans;
FILE *judgemessage = NULL;
FILE *diffpos = NULL;
int judgeans_pos, con_pos;
int judgeans_line, con_line;

void ac() {
  puts("AC");
  exit(0); 
}

void wa() {
  puts("WA");
  exit(0);
}

void wrong_answer(const char *err, ...) {
  wa();
}

void judge_error(const char *err, ...) {
  va_list pvar;
  va_start(pvar, err);
  // If judgemessage hasn't been set up yet, write error to stderr
  if (!judgemessage) judgemessage = stderr;
  vfprintf(judgemessage, err, pvar);
  fprintf(judgemessage, "\n");
  assert(!"Judge Error");
}

bool isfloat(const char *s, double &val) {
  char trash[20];
  double v;
  if (sscanf(s, "%lf%10s", &v, trash) != 1) return false;
  val = v;
  return true;
}

template <typename Stream>
void openfile(Stream &stream, const char *file, const char *whoami) {
  stream.open(file);
  if (stream.fail()) {
    judge_error("%s: failed to open %s\n", whoami, file);
  }
}

FILE *openfeedback(const char *feedbackdir, const char *feedback, const char *whoami) {
  std::string path = std::string(feedbackdir) + "/" + std::string(feedback);
  FILE *res = fopen(path.c_str(), "w");
  if (!res) {
    judge_error("%s: failed to open %s for writing", whoami, path.c_str());
  }
  return res;
}

const char *USAGE = "Usage: %s judge_in judge_ans contestant_ans";

int main(int argc, char **argv) {
  if(argc < 4) {
    judge_error(USAGE, argv[0]);
  }
  openfile(judgein, argv[1], argv[0]);
  openfile(judgeans, argv[2], argv[0]);
  openfile(conans, argv[3], argv[0]);

  bool case_sensitive = false;
  bool space_change_sensitive = false;
  bool use_floats = false;
  double float_abs_tol = -1;
  double float_rel_tol = -1;

  for (int a = 4; a < argc; ++a) {
    if        (!strcmp(argv[a], "case_sensitive")) {
      case_sensitive = true;
    } else if (!strcmp(argv[a], "space_change_sensitive")) {
      space_change_sensitive = true;
    } else if (!strcmp(argv[a], "float_absolute_tolerance")) {
      if (a+1 == argc || !isfloat(argv[a+1], float_abs_tol))
        judge_error(USAGE, argv[0]);
      ++a;
    } else if (!strcmp(argv[a], "float_relative_tolerance")) {
      if (a+1 == argc || !isfloat(argv[a+1], float_rel_tol))
        judge_error(USAGE, argv[0]);
      ++a;
    } else if (!strcmp(argv[a], "float_tolerance")) {
      if (a+1 == argc || !isfloat(argv[a+1], float_rel_tol))
        judge_error(USAGE, argv[0]);
      float_abs_tol = float_rel_tol;
      ++a;
    } else {
      judge_error(USAGE, argv[0]);
    }
  }
  use_floats = float_abs_tol >= 0 || float_rel_tol >= 0;

  judgeans_pos = con_pos;
  judgeans_line = con_line = 1;
   
  std::string judge, team;
  char trash[20];
  while (true) {
    // Space!  Can't live with it, can't live without it...
    while (isspace(judgeans.peek())) {
      char c = (char)judgeans.get();
      if (space_change_sensitive) {
        int d = conans.get();
        if (c != d) {
          wrong_answer("Space change error: got %d expected %d", d, c);
        }
        if (d == '\n') ++con_line;
        ++con_pos;
      }
      if (c == '\n') ++judgeans_line;
      ++judgeans_pos;
    }
    while (isspace(conans.peek())) {
      char d = (char)conans.get();
      if (space_change_sensitive) {
        wrong_answer("Space change error: judge out of space, got %d from team", d);
      }
      if (d == '\n') ++con_line;
      ++con_pos;
    }

    if (!(judgeans >> judge))
      break;

    if (!(conans >> team)) {
      wrong_answer("User EOF while judge had more output\n(Next judge token: %s)", judge.c_str());
    }
     
    double jval, tval;
    if (use_floats && isfloat(judge.c_str(), jval)) {
      if (!isfloat(team.c_str(), tval)) {
        wrong_answer("Expected float, got: %s", team.c_str());
      }
      if(!(fabs(jval - tval) <= float_abs_tol) && 
         !(fabs(jval - tval) <= float_rel_tol*fabs(jval))) {
        wrong_answer("Too large difference.\n Judge: %s\n Team: %s\n Difference: %le\n (abs tol %le rel tol %le)", 
               judge.c_str(), team.c_str(), jval-tval, float_abs_tol, float_rel_tol);
      }
    } else if (case_sensitive) {
      if (strcmp(judge.c_str(), team.c_str()) != 0) {
        wrong_answer("String tokens mismatch\nJudge: \"%s\"\nTeam: \"%s\"", judge.c_str(), team.c_str());
      }
    } else {
      if(strcasecmp(judge.c_str(), team.c_str()) != 0) {
        wrong_answer("String tokens mismatch\nJudge: \"%s\"\nTeam: \"%s\"", judge.c_str(), team.c_str());
      }
    }
    judgeans_pos += judge.length();
    con_pos += team.length();
  }

  if (conans >> team) {
    wrong_answer("Trailing output:\n%s", team.c_str());
  }

  ac();
}