E. Inverse Coloring

Codeforces
IDCF1027E
Time2000ms
Memory256MB
Difficulty
combinatoricsdpmath
English · Original
Chinese · Translation
Formal · Original
You are given a square board, consisting of $n$ rows and $n$ columns. Each tile in it should be colored either white or black. Let's call some coloring _beautiful_ if each pair of adjacent rows are either the same or different in every position. The same condition should be held for the columns as well. Let's call some coloring _suitable_ if it is _beautiful_ and there is no **rectangle** of the single color, consisting of at least $k$ tiles. Your task is to count the number of _suitable_ colorings of the board of the given size. Since the answer can be very large, print it modulo $998244353$. ## Input A single line contains two integers $n$ and $k$ ($1 \le n \le 500$, $1 \le k \le n^2$) — the number of rows and columns of the board and the maximum number of tiles inside the rectangle of the single color, respectively. ## Output Print a single integer — the number of _suitable_ colorings of the board of the given size modulo $998244353$. [samples] ## Note Board of size $1 \times 1$ is either a single black tile or a single white tile. Both of them include a rectangle of a single color, consisting of $1$ tile. Here are the _beautiful_ colorings of a board of size $2 \times 2$ that don't include rectangles of a single color, consisting of at least $3$ tiles: <center>![image](https://espresso.codeforces.com/9123fa0be6c8ef634b9f6a3c1f14009c3c763af7.png)</center>The rest of _beautiful_ colorings of a board of size $2 \times 2$ are the following: <center>![image](https://espresso.codeforces.com/d63dd07185bccbd7fd0ab83b2536ac99904e501c.png)</center>
[{"iden":"statement","content":"你被给定一个由 $n$ 行和 $n$ 列组成的正方形棋盘。每个格子应被染成白色或黑色。\n\n如果每一对相邻行要么完全相同,要么在每个位置上都不同,则称这种染色为 _美丽_ 的。对列也需满足相同的条件。\n\n如果一种染色是 _美丽_ 的,并且不存在由至少 $k$ 个格子组成的、单色的 _矩形_,则称这种染色为 _合适_ 的。\n\n你的任务是计算给定大小棋盘的 _合适_ 染色方案数。\n\n由于答案可能很大,请对 $998244353$ 取模输出。\n\n单行包含两个整数 $n$ 和 $k$($1 lt.eq n lt.eq 500$,$1 lt.eq k lt.eq n^2$)——分别表示棋盘的行数、列数,以及单色矩形中允许的最大格子数。\n\n请输出一个整数——给定大小棋盘的 _合适_ 染色方案数,对 $998244353$ 取模。\n\n大小为 $1 times 1$ 的棋盘要么是一个黑色格子,要么是一个白色格子。这两种情况都包含一个由 $1$ 个格子组成的单色矩形。\n\n以下是大小为 $2 times 2$ 的棋盘中,不包含由至少 $3$ 个格子组成的单色矩形的 _美丽_ 染色方案:\n\n大小为 $2 times 2$ 的棋盘中其余的 _美丽_ 染色方案如下:\n\n"},{"iden":"input","content":"单行包含两个整数 $n$ 和 $k$($1 lt.eq n lt.eq 500$,$1 lt.eq k lt.eq n^2$)——分别表示棋盘的行数、列数,以及单色矩形中允许的最大格子数。"},{"iden":"output","content":"请输出一个整数——给定大小棋盘的 _合适_ 染色方案数,对 $998244353$ 取模。"},{"iden":"examples","content":"输入1 1输出0输入2 3输出6输入49 1808输出359087121"},{"iden":"note","content":"大小为 $1 times 1$ 的棋盘要么是一个黑色格子,要么是一个白色格子。这两种情况都包含一个由 $1$ 个格子组成的单色矩形。以下是大小为 $2 times 2$ 的棋盘中,不包含由至少 $3$ 个格子组成的单色矩形的 _美丽_ 染色方案: 大小为 $2 times 2$ 的棋盘中其余的 _美丽_ 染色方案如下: "}]}
**Definitions** Let $ n, k \in \mathbb{Z}^+ $ with $ 1 \leq n \leq 500 $, $ 1 \leq k \leq n^2 $. Let $ B \in \{0,1\}^{n \times n} $ be a binary matrix representing a coloring of an $ n \times n $ board, where $ 0 $ and $ 1 $ denote white and black, respectively. **Constraints** 1. **Beautiful Coloring Condition**: - For all $ i, j \in \{1, \dots, n\} $, either: - $ B_{i,\cdot} = B_{j,\cdot} $ (rows $ i $ and $ j $ are identical), or - $ B_{i,\cdot} = \overline{B_{j,\cdot}} $ (rows $ i $ and $ j $ are bit-wise complements). - Similarly, for all $ i, j \in \{1, \dots, n\} $, either: - $ B_{\cdot,i} = B_{\cdot,j} $ (columns $ i $ and $ j $ are identical), or - $ B_{\cdot,i} = \overline{B_{\cdot,j}} $ (columns $ i $ and $ j $ are bit-wise complements). 2. **No Monochromatic Rectangle of Size $ \geq k $**: - There does not exist a submatrix $ B[I,J] $, where $ I \subseteq \{1,\dots,n\} $, $ J \subseteq \{1,\dots,n\} $, $ |I| \geq 1 $, $ |J| \geq 1 $, such that: - All entries in $ B[I,J] $ are equal (all 0 or all 1), and - $ |I| \cdot |J| \geq k $. **Objective** Count the number of matrices $ B \in \{0,1\}^{n \times n} $ satisfying both the **beautiful** and **no monochromatic rectangle of size $ \geq k $** conditions, modulo $ 998244353 $.
Samples
Input #1
1 1
Output #1
0
Input #2
2 3
Output #2
6
Input #3
49 1808
Output #3
359087121
API Response (JSON)
{
  "problem": {
    "name": "E. Inverse Coloring",
    "description": {
      "content": "You are given a square board, consisting of $n$ rows and $n$ columns. Each tile in it should be colored either white or black. Let's call some coloring _beautiful_ if each pair of adjacent rows are e",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF1027E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a square board, consisting of $n$ rows and $n$ columns. Each tile in it should be colored either white or black.\n\nLet's call some coloring _beautiful_ if each pair of adjacent rows are e...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "[{\"iden\":\"statement\",\"content\":\"你被给定一个由 $n$ 行和 $n$ 列组成的正方形棋盘。每个格子应被染成白色或黑色。\\n\\n如果每一对相邻行要么完全相同,要么在每个位置上都不同,则称这种染色为 _美丽_ 的。对列也需满足相同的条件。\\n\\n如果一种染色是 _美丽_ 的,并且不存在由至少 $k$ 个格子组成的、单色的 _矩形_,则称这种染色为 _合适_ 的。\\n\\n...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, k \\in \\mathbb{Z}^+ $ with $ 1 \\leq n \\leq 500 $, $ 1 \\leq k \\leq n^2 $.  \nLet $ B \\in \\{0,1\\}^{n \\times n} $ be a binary matrix representing a coloring of an $ n \\times n $ ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}
Full JSON Raw Segments