Codeforces Round #803 (Div. 2)
2 өдрийн дараа |
Codeforces Round #804 (Div. 2)
8 өдрийн дараа |
F. Шалгалтын хариуг зассан нь
хугацааны хязгаарлалт 1 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Програмчлалын багш Дмитрий Олегович дараах бодлогоор оюутнуудаас шалгалт авахаар болов.
Танд $a[1... n, 1... n]$ матрицаар оройнуудын холбоог илэрхийлсэн $n$ оройтой $T$ мод өгөгдөнө. Дараах псевдо кодын үр дүнд үүсэх гаралт нь юу байх вэ?
used[1 ... n] = {0, ..., 0};
procedure dfs(v):
print v;
used[v] = 1;
for i = 1, 2, ..., n:
if (a[v][i] == 1 and used[i] == 0):
dfs(i);
dfs(1);
Дмитрий Олегович шалгалтын хариуг хялбархан шалгах зорилгоор үр дүн нь түүний дуртай $b$ дараалал байх $T$ модыг үүсгэхээр шийджээ. Нөгөө талаас Дмитрий Олегович оролтонд адилхан мод оюутнуудад өгөхийг хүсэхгүй байгаа, учир нь тэд нэг нэгнээсээ хуулж магадгүй юм. Тиймээс Дмитрий дээрх псевдо кодны оролт нь $T$ мод, гаралт нь $b$ дараалал байх ялгаатай $T$ моднуудын тоог олохыг хичээж байна. Та түүнд тусалж чадах уу?
Хэрэв оройнуудын холбоог илэрхийлсэн $a_{1}$ ба $a_{2}$ матрицууд ялгаатай бол $n$ оройтой хоёр модыг ялгаатай гэнэ. Өөрөөр хэлбэл $1 ≤ i, j ≤ n$ ба $a_{1}[i][j] ≠ a_{2}[i][j]$ байх $(i, j)$ хос байна.
Оролт
Эхний мөр нь $b$ дарааллын урт болох эерэг бүхэл $n$ ($1 ≤ n ≤ 500$) тоог агуулна.
Хоёр дахь мөр нь $n$ ширхэг $b_{1}, b_{2}, ..., b_{n}$ ($1 ≤ b_{i} ≤ n$) эерэг бүхэл тоонуудыг агуулна. $b$ нь $n$ хүртэлх тооны сэлгэмэл байна. Өөрөөр хэлбэл $b$ дараалалд $1, 2, ..., n$ тоонууд яг нэг удаа л тохиолдоно. Мөн $b_{1} = 1$ байна.
Гаралт
Дээрх нөхцлийг хангасан моднуудын тоог $10^{9} + 7$-д хуваагаад үлдэгдлийг хэвлэнэ үү.
Орчуулсан: Даариймаа
Жишээ тэстүүд
Оролт
3 1 2 3
Гаралт
2
Оролт
3 1 3 2
Гаралт
1