Выведите его по модулю 998244353

Выведите его по модулю 998244353

Матрица размера $$$n \times m$$$, состоящая только из цифр $$$0$$$ или $$$1$$$ считается красивой , если сумма в каждой подматрице размера $$$2 \times 2$$$ ровно $$$2$$$, т. е. каждый «квадрат» размера $$$2 \times 2$$$ содержит ровно две цифры $$$1$$$ и две цифры $$$0$$$.

Вам задана матрица размера $$$n \times m$$$. Изначально все ячейки матрицы пусты. Обозначим ячейку стоящую на пересечении $$$x$$$-й строки $$$y$$$-го столбца как $$$(x, y)$$$. Вам нужно обрабатывать запросы трех типов:

• $$$x$$$ $$$y$$$ $$$-1$$$ — сделать ячейку $$$(x, y)$$$ пустой;
• $$$x$$$ $$$y$$$ $$$0$$$ — записать цифру $$$0$$$ в ячейку $$$(x, y)$$$, это перезапишет то, что там было ;
• $$$x$$$ $$$y$$$ $$$1$$$ — записать цифру $$$1$$$ в ячейку $$$(x, y)$$$, это перезапишет то, что там было .

После каждого запроса выведите количество способов заполнить пустые ячейки матрицы так, чтобы матрица была красивой . Так как это значение может быть слишком велико, выведите его по модулю $$$998244353$$$.

Первая строка содержит три числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$2 \le n, m \le 10^6$$$; $$$1 \le k \le 3 \cdot 10^5$$$) — количество строк матрицы, количество столбцов и количество запросов соответственно.

Следующие $$$k$$$ строк содержат описания запросов. $$$i$$$-я строка содержит три числа $$$x_i$$$, $$$y_i$$$, $$$t_i$$$ ($$$1 \le x_i \le n$$$; $$$1 \le y_i \le m$$$; $$$-1 \le t_i \le 1$$$) — параметры $$$i$$$-го запроса.

После каждого запроса выведите число — количество способов заполнить пустые ячейки матрицы так, чтобы матрица была красивой по модулю $$$998244353$$$.

Источник

Выведите его по модулю 998244353

$$$n$$$ человек собрались, чтобы провести заседание жюри предстоящего соревнования, $$$i$$$-й член жюри придумал $$$a_i$$$ задач, которыми он хочет поделиться с другими.

Сначала жюри выбирает порядок, которому они будут следовать при обсуждении задач. Пусть это будет перестановка $$$p$$$ чисел от $$$1$$$ до $$$n$$$ (массив размера $$$n$$$, в котором каждое число от $$$1$$$ до $$$n$$$ встречается ровно один раз).

Затем обсуждение происходит следующим образом:

• если у члена жюри $$$p_1$$$ остались задачи, которые нужно рассказать, то он рассказывает одну задачу. В противном случае он будет пропущен.
• если у члена жюри $$$p_2$$$ остались задачи, которые нужно рассказать, то он рассказывает одну задачу. В противном случае он будет пропущен.
• .
• если у члена жюри $$$p_n$$$ остались задачи, которые нужно рассказать, то он рассказывает одну задачу. В противном случае он будет пропущен.
• если остались члены жюри, которые еще не рассказали все свои задачи, то процесс повторяется с самого начала. В противном случае обсуждение заканчивается.

Перестановка $$$p$$$ хорошая, если никто из членов жюри не будет рассказывать две или более задач подряд.

Подсчитайте количество хороших перестановок. Ответ может быть очень большим, поэтому выведите его по модулю $$$998\,244\,353$$$.

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Первая строка набора входных данных содержит одно целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — количество членов жюри.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — количество задач, которые придумал $$$i$$$-й член жюри.

Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Для каждого набора входных данных выведите одно целое число — количество хороших перестановок, взятое по модулю $$$998\,244\,353$$$.

Источник

Пицца

Вася собирается приготовить пиццу для m своих друзей. В распоряжении Васи есть n дополнительных ингредиентов, каждый из которых можно либо положить в пиццу, либо нет. Вася может как использовать все ингредиенты, так и приготовить пиццу совсем без дополнительных ингредиентов. Таким образом, Вася может приготовить пиццу 2 n различными способами.

Однако не любая пицца обрадует друзей Васи. А именно, каждый друг Васи сформировал список из пожеланий вида «хочу, чтобы пицца была с ингредиентом t» или «хочу, чтобы ингредиента t в пицце не было». Друзья Васи непривередливы, поэтому пицца, при приготовлении которой было учтено хотя бы одно пожелание из списка друга, обрадует его.

Вася хочет приготовить пиццу таким образом, чтобы хотя бы одно пожелание от каждого из его друзей было учтено.

Найдите, сколькими способами Вася может приготовить пиццу, чтобы обрадовать всех своих друзей. Так как это число может быть слишком большим, выведите его остаток от деления на 998244353.

Входные данные

В первой строке входных данных находятся целые числа n и m — количество ингредиентов и количество друзей Васи, соответственно (1 ≤ n ≤ 1000, 1 ≤ m ≤ 20).

Каждая из следующих m строк соответствует одному из друзей Васи и содержит целое число a_i — количество пожеланий в списке, за которым следует a_i чисел b_i,j — описание пожеланий в списке (1 ≤ a_i ≤ 100, -n ≤ b[i,j] ≤ n, b_i,j ̸= 0)**. Если ** b[i,j] ** положительно, то **i**-й друг имеет пожелание «хочу, чтобы пицца была с ингредиентом ** b[i,j] **», если отрицательно, то **i**-й друг имеет пожелание «хочу, чтобы ингредиента ** -b[i,j]` в пицце не было».

Никакой ингредиент не входит в список одного друга более одного раза.

Выходные данные

Выведите количество различных способов приготовить пиццу, которые обрадовали бы всех друзей Васи, взятое по модулю 998244353.

Замечание

В первом примере подходят следующие наборы ингредиентов: (1), (3), (1; 3), (1; 4), (1; 3; 4).

Во втором примере ингредиента 42 не должно быть в пицце, а остальные ингредиенты могут как присутствовать, так и нет. Ответ равен остатку от деления 267 на 998244353.

Источник

Выведите его по модулю 998244353

As far as I know, 998244353 allows you to do interesting stuff related to polynomial multiplication I haven’t fully studied yet. See this CF tutorial and this note in P etr’s blog.

Other times, 998244353 is used because it’s prime, much like 10 9 + 7 , or 10 9 + 9 , or 10 6 + 69 . There can also be a mind-game factor involved: one time, I thought a problem needed the above tricks to be solved simply because the modulo was 998244353 , but in the end, I was fooled!

Why it appears often in educational rounds? I don’t know, you’ll have to ask the setters for that.

This is nice because it lets you do Fast Fourier Transforms (mod p) using only the integers. In other words, the setters don’t want to give away whether the problem is supposed to be done using FFT or not.

the setters don’t want to give away whether the problem is supposed to be done using FFT or not.

I think FFT can be done even with modulo 10 9 + 7 . You can do it by FFT with some large two modulos, for example, modulo 1 + 7·2 26 and 1 + 5·2 25 . Then you can restore the value using Chinese Remainder Theorem (or extended Euclidean algorithm). And finally modulo it by 10 9 + 7 .
Obviously, this way also works for 10 9 + 9 , 998244353 , or some other modulos. But, if the modulo is 10 9 + 7 , I think that some people may think «the solution is definitely not FFT» even if FFT is actually involved. Finally, I think taking modulo with 10 9 + 7 or 10 9 + 9 is the best way to hide the solution (whether FFT or not).

Recently, problem setters found that giving every problem modulo 998244353 is the best way to hide the solution 🙁 Now 998244353 doesn’t mean anything. There are so many problems not using FFT but having modulo 998244353.

Sorry, I wasn’t necessarily talking about polynomial multiplication: I agree you can do CRT to do polynomial multiplication mod 10 9 + 7 say. 998244353 is special because you can actually do a fourier transform with a 2 n -th root of unity.

Also, I would say that I also agree that it’s just more convenient to have a template to do polynomial multiplication modulo p for any prime p .

Источник

Выведите его по модулю 998244353

Подмассив массива $$$a$$$ с индекса $$$l$$$ по индекс $$$r$$$ — это массив $$$[a_l, a_, \dots, a_]$$$. Количество вхождений массива $$$b$$$ в массива $$$a$$$ — это количество таких подмассивов массива $$$a$$$, которые равны $$$b$$$.

Вам даны $$$n$$$ массивов $$$A_1, A_2, \dots, A_n$$$; их элементы — целые числа от $$$1$$$ до $$$k$$$. Вы должны построить массив $$$a$$$ из $$$m$$$ целых чисел от $$$1$$$ до $$$k$$$ таким образом, чтобы для каждого заданного массива $$$A_i$$$ выполнялось следующее условие: количество вхождений массива $$$A_i$$$ в массив $$$a$$$ не меньше , чем количество вхождений каждого непустого подмассива $$$A_i$$$ в $$$a$$$ (по отдельности). Обратите внимание, что если $$$A_i$$$ не входит в $$$a$$$, и никакой подмассив $$$A_i$$$ не входит в $$$a$$$, это условие выполняется для $$$A_i$$$.

Ваша задача — посчитать количество различных массивов $$$a$$$, удовлетворяющих этим условиям, и вывести его по модулю $$$998244353$$$.

В первой строке заданы три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$1 \le n, m, k \le 3 \cdot 10^5$$$) — количество заданных массивов, требуемое количество элементов в массиве $$$a$$$, и верхнее ограничение на элементы массивов.

Затем следуют $$$n$$$ строк. $$$i$$$-я строка задает массив $$$A_i$$$. Первое число в $$$i$$$-й строке — $$$c_i$$$ ($$$1 \le c_i \le m$$$), количество элементов в массиве $$$A_i$$$; затем следуют $$$c_i$$$ целых чисел от $$$1$$$ до $$$k$$$ — элементы массива $$$A_i$$$.

Дополнительное ограничение на входные данные: $$$\sum\limits_^n c_i \le 3 \cdot 10^5$$$; то есть общее количество элементов в заданных массивах не превосходит $$$3 \cdot 10^5$$$.

Выведите одно целое число — количество различных массивов $$$a$$$, удовлетворяющих данным условиям, по модулю $$$998244353$$$.

Источник