Recurrences, NTT and expectation

Questions 1 to 5 of 8

1. 1. An AI tool says that raising a 10 by 10 matrix to the power 10^18 takes about 10^18 steps, one per unit of the exponent. Using the method in this module, what is the right estimate?

   About 10^18 steps, since each unit of the exponent is one multiplicationAbout 1,000 steps, since the exponent is applied to one 10 by 10 product onlyAbout 120,000 steps: about 120 products of 10 by 10 matrices, each costing 10 cubedAbout 60 steps, one per bit, because each bit is a single number
2. 2. Which statements about the matrix exponentiation in this module are true? Select all that apply.

   Pick every answer that is true.

   The transition matrix has a fixed size k, and the same rule applies at every stepThe method works for f(n) = n times f(n - 1), because the rule is linearAn exponent of 10^18 has 60 bits, so the squaring loop runs at most about 60 timesSumming 19 products of two residues below 998244353 always fits in an unsigned 64-bit integer
3. 3. The NTT modulus is p = 998244353. What is the largest power of two that divides p - 1 = 998244352? Enter the number.

   Type a number.

4. 4. An AI tool wrote an NTT for length 2^19 with the modulus 1000000007, because many snippets online use it. Which fact shows that this cannot work?

   1000000007 is prime, so every inverse exists and the transform is exactThe modulus is larger than 998244353, so products overflow 64 bits1000000006 = 2 times 500000003, so the only power of two dividing p - 1 is 2, and no root of order 2^19 existsThe modulus is odd, and the NTT needs an even modulus
5. 5. Put the steps of multiplying two polynomials with the NTT in the order they run.

   Use the arrows to put the steps in order.

   1. 1.Run the forward NTT on both arrays↑↓
   2. 2.Run the inverse NTT on the product↑↓
   3. 3.Multiply every value by the inverse of the length↑↓
   4. 4.Pad both arrays to a power-of-two length of at least a + b - 1↑↓
   5. 5.Multiply the two transforms value by value↑↓