codeforces-scrape

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

1081C.md (1880B)


      1 Source: https://codeforces.com/problemset/problem/1081/C
      2 
      3 C. Colorful Bricks
      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 On his free time, Chouti likes doing some housework. He has got one new task, paint some bricks in the yard.
     22 
     23 There are $n$ bricks lined in a row on the ground. Chouti has got $m$ paint buckets of different colors at hand, so he painted each brick in one of those $m$ colors.
     24 
     25 Having finished painting all bricks, Chouti was satisfied. He stood back and decided to find something fun with these bricks. After some counting, he found there are $k$ bricks with a color different from the color of the brick on its left (the first brick is not counted, for sure).
     26 
     27 So as usual, he needs your help in counting how many ways could he paint the bricks. Two ways of painting bricks are different if there is at least one brick painted in different colors in these two ways. Because the answer might be quite big, you only need to output the number of ways modulo $998\,244\,353$.
     28 
     29 Input
     30 
     31 The first and only line contains three integers $n$, $m$ and $k$ ($1 \leq n,m \leq 2000, 0 \leq k \leq n-1$) — the number of bricks, the number of colors, and the number of bricks, such that its color differs from the color of brick to the left of it.
     32 
     33 Output
     34 
     35 Print one integer — the number of ways to color bricks modulo $998\,244\,353$.
     36 
     37 Examples
     38 
     39 Input
     40 
     41 ```
     42 3 3 0
     43 ```
     44 
     45 Output
     46 
     47 ```
     48 3
     49 ```
     50 
     51 Input
     52 
     53 ```
     54 3 2 1
     55 ```
     56 
     57 Output
     58 
     59 ```
     60 4
     61 ```
     62 
     63 Note
     64 
     65 In the first example, since $k=0$, the color of every brick should be the same, so there will be exactly $m=3$ ways to color the bricks.
     66 
     67 In the second example, suppose the two colors in the buckets are yellow and lime, the following image shows all $4$ possible colorings.
     68 
     69  ![](https://espresso.codeforces.com/f2b62925cc9bfa9f420c66d8f1f0ce20219e0c11.png)