Good Bye 2022: 2023 is NEAR |
---|
Закончено |
Косия и Махиру играют в игру с тремя массивами $$$a$$$, $$$b$$$ и $$$c$$$ длины $$$n$$$. Каждый элемент $$$a$$$, $$$b$$$ и $$$c$$$ — целое число от $$$1$$$ до $$$n$$$ включительно.
Игра состоит из $$$n$$$ раундов. В $$$i$$$-м раунде они делают следующие ходы:
Пусть $$$d_i$$$ — число, выбранное Махиру в $$$i$$$-м раунде. Если $$$d$$$ является перестановкой$$$^\dagger$$$, Косия выигрывает. Иначе выигрывает Махиру.
Сейчас выбраны только массивы $$$a$$$ и $$$b$$$. Являясь ярым поклонником Косии, вы хотите выбрать массив $$$c$$$ так, чтобы Косия выиграла. Вычислите количество таких $$$c$$$ по модулю $$$998\,244\,353$$$.
Обратите внимание, что Косия и Махиру играют оптимально.
$$$^\dagger$$$ Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \leq n \leq {10}^5$$$) — размеры массивов.
Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq n$$$).
Третья строка содержит $$$n$$$ целых чисел $$$b_1, b_2, \dots, b_n$$$ ($$$1 \leq b_i \leq n$$$).
Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$${10}^5$$$.
Выведите одно целое число — количество массивов $$$c$$$, при которых выигрывает Косия, по модулю $$$998\,244\,353$$$.
231 2 21 3 353 3 1 3 44 5 2 5 5
6 0
В первом примере есть $$$6$$$ массивов $$$c$$$, при которых выигрывает Косия: $$$[1, 2, 3]$$$, $$$[1, 3, 2]$$$, $$$[2, 2, 3]$$$, $$$[2, 3, 2]$$$, $$$[3, 2, 3]$$$, $$$[3, 3, 2]$$$.
Во втором примере можно показать, что нет массивов $$$c$$$, при которых выигрывает Косия.
Название |
---|