Bomboni
레이팅 미적용의견: 0
Iva is a big fan of candy! In front of her is an \(n\) times \(n\) field filled with candy and
obstacles. Iva is currently in the upper left cell of the field and by moving only
down and right she will travel to the lower right cell. The cell Iva is currently in
does not contain an obstacle.
In every cell, there is either an obstacle or a piece of candy with a number written
on it. Iva will eat all the candy she gets her hands on during her trip (including
the candy in the first and last cell) and then multiply all the numbers on them.
Iva knows her favourite number is \(k\) and she wants the product of the numbers on the candy she has eaten
to be divisible by \(k\). She wants to know how many such paths there are. Because that number can be
huge, she is interested in it modulo 998 244 353.
Subtask 1 (13 points): n, k, ai,\(j \le 20\)
Subtask 2 (17 points): n, \(k \le 20\)
Subtask 3 (33 points): \(k \le 20\)
Subtask 4 (47 points): No additional constraints
The first line contains two integers \(n\) and \(k\) (\(1 \le n \le 500\), \(1 \le k \le 10^{6}\)), which denote the size of the field
and Iva’s favourite number.
In each of the next \(n\) lines, there are \(n\) numbers describing the \(i-th\) row of the field (−\(1 \le a\)i,\(j \le 10^{6}\)). If
\(a\)i,j = −1, then that cell contains an obstacle, otherwise \(1 \le a\)i,\(j \le 10^{6}\) and that cell contains a piece of
candy with that number.
Print a single line with the required number from the task.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 13점 | n, k, ai,\(j \le 20\) |
2 | 17점 | n, \(k \le 20\) |
3 | 33점 | \(k \le 20\) |
4 | 47점 | No additional constraints |
2 2
3 2
1 423 6
5 2 -1
7 3 6
-1 3 13Clarification of the second example:
There are three possible paths such that the product is divisible by 6: 5· 2· 3· 3· 1, 5· 2· 3· 6· 1, 5· 7· 3· 6· 1.
평가 및 의견
Bomboni
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Bomboni