Yet Another Array Problem#12363

Yet Another Array Problem (Editorial)

Problem Author:	Ramen
Prepared by:	Ramen
Edited by:	Hasan Saleh (MathModel)

Solution

To calculate the total number of arrays, we first determine the number of valid $m$ -digit integers ( $A$ ) that can be formed using the provided set of $k$ digits: if the set excludes zero, there are $k^{m}$ k^m possibilities, but if it includes zero, we must exclude it from the first position, resulting in $A = (k - 1) \cdot k^{m - 1}$ A = (k-1) \cdot k^{m-1}. Since we are forming an array of length $n$ and each of the $n$ positions can be filled by any of these $A$ valid numbers, the total number of possible arrays is simply the product of $A$ for each position, resulting in $A^{n}$ A^n. Because this value grows exponentially, we compute the result using modular exponentiation ( $A^{n} (mod 1 0^{9} + 7)$ A^n \pmod{10^9 + 7}) to ensure efficiency and numerical stability.

Complexity $O (m + lo g (n))$ O(m+\log(n)).

MOD=10**9+7
for _ in range(int(input())):
    m,n=map(int,input().split())
    a=list(map(int,input().split()))
    k=len(a)
    if 0 in a:
        A=(k-1)*pow(k,m-1,MOD)%MOD
    else:
        A=pow(k,m,MOD)
    print(pow(A,n,MOD))

Python