| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 4 초 | 2048 MB | 61 | 37 | 8 | 29.630% |
You are given a set $S$ containing $N$ different positive integers. You are also given a positive integer $K$ and a prime number $M$.
An array is said to be honourable if each of its elements is in $S$, and the product of all elements in the array is $K$ modulo $M$.
For a given integer $L$, count the number of different honourable arrays with length $L$. Two arrays of length $L$ are said to be different if there exists an index such that the elements in both arrays differ at that index. Output the count modulo $998244353$.
The first line contains four integers $N$, $K$, $M$, and $L$ ($1 \leq N, K < M$; $2 \leq M \leq 100000$; $1 \leq L \leq 10^9$; $M$ is a prime). The second line contains $N$ different integers representing $S$, each is a positive integer less than $M$.
Output an integer representing the number of different honourable arrays modulo $998244353$.
2 1 3 4 1 2
8
2 1 3 1000 1 2
510735315
Explanation of Sample 1: the different honourable arrays of size $4$ are: $[1, 1, 1, 1]$, $[1, 1, 2, 2]$, $[1, 2, 1, 2]$, $[1, 2, 2, 1]$, $[2, 1, 1, 2]$, $[2, 1, 2, 1]$, $[2, 2, 1, 1]$, $[2, 2, 2, 2]$.
ICPC > Regionals > Asia Pacific > Indonesia > Indonesia National Contest > INC 2025 L번