Characteristic Polynomial Verification codechef solution- 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)

Characteristic Polynomial Verification solution codechef

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+CM1AM10N(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: Characteristic Polynomial Verification solution codechef 

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

Characteristic Polynomial Verification solution codechef

  • 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,CM1C0,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.

Characteristic Polynomial Verification solution codechef

For each test case, output on a single line YES if the equation C0In+C1A+C2A2+CM1AM10N(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

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

Characteristic Polynomial Verification solution codechef

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

Characteristic Polynomial Verification solution codechef

 

YES
NO

Characteristic Polynomial Verification solution codechef

Both test cases have the same co-efficients. Since 9982443512(mod998244353)998244351≡−2(mod998244353) and 9982443485(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 2I25A+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, 2I25A+A2=[5335]−2I2−5A+A2=[−5−3−3−5]. Clearly none of the entries are divisible by 998244353998244353, so the answer is NO.

Leave a Comment