Zig-zag (Problem M, The 2024 ICPC Asia Pacific Championship, 2024)
Time limit: 12 sec
Author: Kevin Charles Atienza

# Problem Statement

Zack’s Zergonomics Zegree has taught him that the optimal way to display items in a store is to stack them into a zig-zag pattern.

Zack needs to display $n$ boxes lined up on the storefront, each one containing an action figure. These boxes can be stacked on top of one another, and they are identical and indistinguishable from each other. His goal is to decide the number of stacks, and then stack up the boxes such that each stack is non-empty, and the numbers of boxes in the stacks form a zig-zag sequence.

Formally, if there are $s$ ($s \ge 1$) stacks numbered $1$ to $s$ from left to right, and stack $i$ contains $a_i$ boxes, then the following conditions must be satisfied:

- $a_i \ge 1$ for each $i$ from $1$ to $s$,
- $a_1 + a_2 + \dots + a_s = n$, and
- at least one of the following is true:
  - $a_1 < a_2 > a_3 < a_4 > \dots$, or
  - $a_1 > a_2 < a_3 > a_4 < \dots$

For example, for $n = 6$, there are 12 ways as illustrated by Figure M.1:

![Figure M.1: All 12 possible ways for n = 6.](icpc-apac-2024-zigzag-1.png)

Find the number of different ways Zack can stack $n$ boxes modulo $998\ 244\ 353$.

Two ways are considered the same if and only if the number of stacks is the same, and pairs of stacks at the same positions have the same number of boxes.

# Input

The first line of input contains one integer $t$ ($1 \le t \le 300\ 000$) representing the number of test cases. After that, $t$ test cases follow. Each of them consists of a single line containing one integer $n$ ($1 \le n \le 300\ 000$).

# Output

For each test case, output an integer representing the number of different ways to stack $n$ boxes modulo $998\ 244\ 353$.

# Sample Input #1
```
4
5
6
7
890
```
# Sample Output #1
```
7
12
19
502674609
```
### Explanation for the sample input/output #1

The value of n on the second test case is 6, and the 12 ways are illustrated in the problem description.

Sample inputs:
4
5
6
7
890

Sample outputs:
7
12
19
502674609

# Solution Analysis
Analysis author: Kevin Charles Atienza

Here, we’ll only describe how to count *even-length* partitions of $n$ such that $a_1 < a_2 > a_3 < a_4 > a_5 < \dots$.  
There are only a few other kinds of partitions and they can all be handled similarly. Also, let $N := 300\ 000$.

Instead of counting partitions satisfying $a_1 < a_2 > a_3 < a_4 > a_5 < \dots$, it’s easier to count partitions satisfying $a_1 < a_2 \le a_3 < a_4 \le a_5 < \dots$. Let’s call even-length partitions satisfying the latter *almost increasing*. Once we have computed the latter, the former can be computed by inclusion-exclusion. Specifically, we’re counting partitions satisfying $a_1 < a_2\ ?\ a_3 < a_4\ ?\ a_5 < \dots$ where each “?” is either “no condition”, or “$\le$”, and in the latter case, the whole term is weighted by $-1$ (because of inclusion-exclusion).

Formally, let the *weight* of an almost-increasing partition be $(-1)^k$ where $k$ is the number of times “$\le$” appears, and let $a(n)$ be the sum of the weights of all almost-increasing partitions of $n$. Then every partition satisfying “$a_1 < a_2\ ?\ a_3 < a_4\ ?\ a_5 < \dots$” is just a conjunction of some number $k$ of almost-increasing partitions. Thus, the number $c(n)$ of partitions of $n$ satisfying $a_1 < a_2 > a_3 < a_4 > a_5 < \dots$ is

$$
c(n) = \sum_{k=0}^{\infty} \sum_{n_1 + \dots + n_k = n \atop n_i \ge 0} a(n_1)a(n_2) \dots a(n_k),
$$

where the inner sum is actually a $k$-fold sum. The inclusion-exclusion is handled by the weights. Now, notice that this is a convolution and can be stated nicely in terms of generating functions! Let $A(x) := \sum_{n \ge 0} a(n)x^n$ and $C(x) := \sum_{n \ge 0} c(n)x^n$. Then the above translates to

$$
C(x) = \sum_{k=0}^{\infty} A(x)^k = \frac{1}{1 - A(x)}.
$$

Thus, if we’re able to compute $A(x)$, we’re also able to compute $C(x)$ with a single generating function inverse in $O(N \log N)$.

The values $a(n)$ for $n \le N$ can be computed with DP by noticing that for an almost-increasing partition $a$ of $n$, $a_i \ge i/2$ for all $i$, and thus its length is $O(\sqrt{n})$. Thus, we can compute them with DP by finding a recurrence for $a(n, \ell)$, the sum of the weights of almost-increasing partitions with sum $n$ and length $\ell$. Because $n \le N$ and $\ell \le 2\sqrt{N}$, with an $O(1)$ transition this gives an $O(N^{1.5})$-time algorithm.

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();
}