Олимпиадный тренинг

Задача . F. Количество кубов


Задача

Темы: дп Комбинаторика математика теория чисел *2700

Рассмотрим прямой параллелепипед с размерами сторон \(a\), \(b\) и \(c\), состоящий из единичных кубиков \(k\) различных цветов. Мы можем делать циклические сдвиги параллелепипеда в любом измерении и в любой комбинации\(^{\text{∗}}\).

Имеется \(d_i\) кубиков \(i\)-го цвета (\(1 \le i \le k\)). Сколько можно составить из этих кубиков различных параллелепипедов с данными размерами сторон, никакие два из которых нельзя совместить комбинацией сдвигов?

\(^{\text{∗}}\)На рисунке:

  • Слева-вверху показан вид сверху у изначального параллелепипеда. Нижние слои будут сдвигаться по аналогии с верхним.
  • Справа-вверху показан вид сверху у параллелепипеда, сдвинутого направо на \(1\).
  • Слева-внизу показан вид сверху у параллелепипеда, сдвинутого вниз на \(2\).
  • Справа-внизу показан вид сверху у параллелепипеда, сдвинутого направо на \(1\) и вниз на \(2\).
Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число \(t\) (\(1 \le t \le 100\)) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит четыре целых числа: \(a\), \(b\), \(c\) и \(k\) (\(1 \le a, b, c \le 3 \cdot 10^6\); \(a \cdot b \cdot c \le 3 \cdot 10^6\); \(1 \le k \le 10^6\)) — три стороны параллелепипеда и количество цветов единичных кубиков.

Вторая строка каждого набора входных данных содержит \(k\) целых чисел \(d_1, d_2, \ldots, d_k\) (\(1 \le d_1 \le d_2 \le \ldots \le d_k \le 3 \cdot 10^6\)) — элементы массива \(d\): количества кубиков заданного цвета.

Гарантируется, что в каждом наборе входных данных сумма элементов массива \(d\) равна \(a \cdot b \cdot c\).

Гарантируется, что сумма значений \(k\) по всем наборам входных данных не превосходит \(10 ^ 6\).

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

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

Примечание

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

Возможные параллелепипеды во втором наборе

Примеры
№Входные данныеВыходные данные
1 6
1 1 1 1
1
6 1 1 3
1 2 3
12 1 1 3
2 4 6
3 3 1 2
3 6
2 3 3 2
6 12
72 60 96 4
17280 86400 120960 190080 
1
10
1160
12
1044
231490207

time 5000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w643
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет