Блог пользователя aloo_parantha

Автор aloo_parantha, история, 4 года назад, По-английски

Problem Link : https://www.codechef.com/ENFE2020/problems/ECFEB207

Problem : Chef bought a rectangular checkered board of size N rows and M colums and color pens of P different colors. He randomly painted each cell with any of the P colors. When he was done painting all the cells, he noticed something very interesting property. For any vertical line that divides the board into two non-empty boards, the number of distinct colors in both the parts was the same.

Now, chef wonders in how many ways can he color the board using only the colors available such that this interesting property holds.

1≤N,M≤1000 1≤P≤10^6

Output : print the answer to the problem modulo 1000000007.

E.g. INPUT : 2 2 2 OUTPUT: 8

My Approach: I think, we can decide some colours which are to be arranged in the first column, and then each of the selected colour should be present in the last column at least once in any order , and the rest of the (N) X (N-2) matrix can have any distribution with these selected colours, because now,no matter wherever we draw a vertical line , number of distinct colours in the two parts will be same…I couldn’t implement it. Can anyone please let me know, if this approach is correct and how can I implement it. Or suggest some better approach…

  • Проголосовать: нравится
  • -2
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone please help me with this problem???

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by aloo_parantha (previous revision, new revision, compare).