October Long Challenge Characteristic Polynomial Verification

Characteristic Polynomial Verification CHARVER

Given an array CC of MM integers and a square matrix AA (with integer entries) of dimension N×NN×N, verify whether the following equation is true,C0IN+C1A+C2A2+…CM−1AM−1≡0N(mod998244353)C0IN+C1A+C2A2+…CM−1AM−1≡0N(mod998244353)

where 0N0N is the square null matrix (matrix in which all elements are zero) and ININ is the identity matrix, both having dimensions N×NN×N.

Note:

  • Two matrices A,BA,B each with integer entries are said to be congruent modulo MM iff all entries of A−BA−B are divisible by MM. This is denoted as A≡B(modM)A≡B(modM).
  • Since the input-output is large, prefer using fast input-output methods.

Input Format

  • The first line contains TT denoting the number of test cases. Then the test cases follow.
  • The first line of each test case contains a single integer MM denoting the length of CC.
  • The second line of each testcase contains MM space separated integers, C0,C1,…CM−1C0,C1,…CM−1 representing the array CC.
  • The third line of each testcase contains a single integer NN denoting the size of the square matrix AA.
  • The ii-th line of the next NN lines contains NN space-separated integers Ai,1,Ai,2,…,Ai,NAi,1,Ai,2,…,Ai,N denoting the elements of the ii-th row of the matrix AA.

Output Format

For each test case, output on a single line YES if the equation C0In+C1A+C2A2+…CM−1AM−1≡0N(mod998244353)C0In+C1A+C2A2+…CM−1AM−1≡0N(mod998244353) satisfies, and NO otherwise.

Output is case insensitive, i.e., you may print each character of the string in uppercase or lowercase (for example, the strings “yEs”, “yes”, “Yes” and “YES” will all be treated as identical).

Constraints

  • 1≤T≤2001≤T≤200
  • 1≤N≤10001≤N≤1000
  • 1≤M≤111≤M≤11
  • 0≤Ci<9982443530≤Ci<998244353
  • 0≤Ai,j<9982443530≤Ai,j<998244353
  • Sum of NN over all test cases does not exceed 20002000.

Subtasks

Subtask 1 (100 points): Original constraints

Sample Input 1 

2
3
998244351 998244348 1
2
1 2
3 4
3
998244351 998244348 1
2
1 1
1 1

Sample Output 1 

YES
NO

Explanation

Both test cases have the same co-efficients. Since 998244351≡−2(mod998244353)998244351≡−2(mod998244353) and 998244348≡−5(mod998244353)998244348≡−5(mod998244353), for convenience of explanation, we shall take the co-efficients as −2,−5,1−2,−5,1. Note that this does not affect the answer.

Test case 11: The given matrix, A=[1324]A=[1234], satisfies the equation −2I2−5A+A2=02−2I2−5A+A2=02, so the answer is YES.

Test case 22: For the given matrix, A=[1111]A=[1111], the left hand side of the equation evaluates to, −2I2−5A+A2=[−5−3−3−5]−2I2−5A+A2=[−5−3−3−5]. Clearly none of the entries are divisible by 998244353998244353, so the answer is NO.

CLICK BELOW!!

Solution will be updated soon mean while keep trying..

October Long Challenge 2021

Leave a Comment