No.243 Attendance Number (2)
タグ : / 解いたユーザー数 85
作問者 :
Problem Statement
There is a class with $N$ students. The students are named $S_0$ through $S_{N-1}$.
We want to assign each student an attendance number from $0$ to $N-1$.
However, each student has 1 number they dislike and do not want as their attendance number.
Find the number of ways to assign attendance numbers such that no student is assigned their disliked number, modulo \({\rm mod}\ 10^{9}+7\).
Input
$N$
$A_0$
$A_1$
$\vdots$
$A_{N-1}$
The first line contains the number of students $N$. $1 \le N \le 5000$.
The following $N$ lines give $A_i$, the number disliked by $S_i$. $0 \le A_i \le 4999$.
Output
Output the number of ways to assign attendance numbers such that no student is assigned their disliked number, \({\rm mod}\ 10^{9}+7\).
Sample
Sample 1
Input
3 0 1 2
Output
2
There are 2 ways to assign the numbers: 1 2 0 and 2 0 1.
Sample 2
Input
4 3 3 3 3
Output
0
Sample 3
Input
5 1 1 1 0 1
Output
24
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。