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+…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:

  • 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 –  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,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 – Output Format

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).

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

Characteristic Polynomial Verification solution codechef – Explanation

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.


 

Characteristic Polynomial Verification solution codechef

Leave a Comment