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 