Characteristic Polynomial Verification

by

Characteristic Polynomial Verification CHARVER

Given an array C of M integers and a square matrix A (with integer entries) of dimension N×N, verify whether the following equation is true, C0IN+C1A+C2A2+…CM−1AM−1≡0N(mod998244353) where 0N is the square null matrix (matrix in which all elements are zero) and IN is the identity matrix, both having dimensions N×N.

Note:

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

Input Format

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

Output Format

For each test case, output on a single line YES if the equation 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≤200
  • 1≤N≤1000
  • 1≤M≤11
  • 0≤Ci<998244353
  • 0≤Ai,j<998244353
  • Sum of N over all test cases does not exceed 2000.

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) and 998244348≡ -5 (mod998244353), for convenience of explanation, we shall take the co-efficients as -2,-5,1. Note that this does not affect the answer.
  • Test case 1: The given matrix, A=[1324], satisfies the equation -2I2-5A+A2=02, so the answer is YES.
  • Test case 2: For the given matrix, A=[1111], the left hand side of the equation evaluates to, −2I2−5A+A2=[−5−3−3−5]. Clearly none of the entries are divisible by 998244353, so the answer is NO.

October Long Challenge 2021

Leave a Comment

nine − 6 =