codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1051D.md (1274B)


      1 Source: https://codeforces.com/problemset/problem/1051/D
      2 
      3 D. Bicolorings
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You are given a grid, consisting of $2$ rows and $n$ columns. Each cell of this grid should be colored either black or white.
     22 
     23 Two cells are considered neighbours if they have a common border and share the same color. Two cells $A$ and $B$ belong to the same component if they are neighbours, or if there is a neighbour of $A$ that belongs to the same component with $B$.
     24 
     25 Let's call some bicoloring beautiful if it has exactly $k$ components.
     26 
     27 Count the number of beautiful bicolorings. The number can be big enough, so print the answer modulo $998244353$.
     28 
     29 Input
     30 
     31 The only line contains two integers $n$ and $k$ ($1 \le n \le 1000$, $1 \le k \le 2n$) — the number of columns in a grid and the number of components required.
     32 
     33 Output
     34 
     35 Print a single integer — the number of beautiful bicolorings modulo $998244353$.
     36 
     37 Examples
     38 
     39 Input
     40 
     41 ```
     42 3 4
     43 ```
     44 
     45 Output
     46 
     47 ```
     48 12
     49 ```
     50 
     51 Input
     52 
     53 ```
     54 4 1
     55 ```
     56 
     57 Output
     58 
     59 ```
     60 2
     61 ```
     62 
     63 Input
     64 
     65 ```
     66 1 2
     67 ```
     68 
     69 Output
     70 
     71 ```
     72 2
     73 ```
     74 
     75 Note
     76 
     77 One of possible bicolorings in sample $1$:
     78 
     79  ![](https://espresso.codeforces.com/2ecd9d930a237f1796ff6627842f7d2672b69627.png)