| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1.5 초 (추가 시간 없음) | 1024 MB | 503 | 219 | 200 | 45.249% |
자연수 $N$이 주어질 때, 1ドル$ 이상 $N$ 이하의 자연수 $i$에 대해 정의되는 함수 $f$가 있다. 모든 $i$에 대해 $f\left(i\right)$ 또한 1ドル$ 이상 $N$ 이하의 자연수다.
$f$에 대한 함수 그래프를 정점 $i$에서 정점 $f\left(i\right)$로 향하는 단방향 간선들로 이루어진 그래프라 부르자. 이 그래프는 $f$에 따라 유일하게 결정됨을 알 수 있다.
우리는 함수 $f$를 알지 못하지만, $f$에 대한 함수 그래프에서 모든 정점에 대한 도달 가능성 정보를 가지고 있다. 정점 $u$에서 정점 $v$에 도달 가능하다는 것은 0ドル$개 이상의 간선을 통해 정점 $u$에서 정점 $v$로 갈 수 있다는 뜻이다.
함수 $f$로 가능한 경우의 수를 구하여라.
첫 줄에 $N$이 주어진다. (1ドル \leq N \leq 500$)
그 후, $N$개의 줄에 걸쳐 $f$에 대한 함수 그래프에서 도달 가능성 정보가 공백으로 구분되어 주어진다. $i$번째 줄의 $j$번째 수는 $i$에서 $j$에 도달 가능하면 1ドル,ドル 그렇지 않으면 0ドル$이다. 가능한 함수 $f$가 존재하지 않는 경우는 주어지지 않는다.
함수 $f$로 가능한 경우의 수를 10ドル^9 + 7$로 나눈 나머지를 출력한다.
6 1 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 1 1 1 1 1 0 0 0 0 0 0 1
6
9 1 0 1 1 0 0 0 0 0 1 1 1 1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 1 1 1 1 1 0 0 1 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 1 0 0 0 1
6
University > 전국 대학생 프로그래밍 대회 동아리 연합 > UCPC 2020 C번