Polynomials, Moduli & Hashing Sorcery

NTT-friendly primes like 998244353, oversized convolutions, recovering linear recurrences, fast modular reduction, and hashes that survive anti-tests.

0 / 8 solved

Question Tags Difficulty Success

1. XOR Undoes Itself

zobrist-hashingincremental-update +2

Medium —

2. The Default NTT Prime

ntt998244353 +2

Hard —

3. Four Billion Positions

zobrist-hashingbirthday-bound +2

Hard —

4. Three Primes And Garner

nttchinese-remainder-theorem +2

Hard —

5. Montgomery Wants Odd

montgomery-multiplicationbarrett-reduction +2

Hard —

6. Never Hash With Polynomials

tree-hashingtree-isomorphism +2

Hard —

7. The Length Ceiling

ntttransform-length +2

Insane 40%

8. Two M Terms

berlekamp-masseylinear-recurrence +2

Insane —

zobrist-hashingincremental-updatexorstate-hashingntt998244353primitive-rootmodular-arithmeticbirthday-boundcollision-probabilityhashingchinese-remainder-theoremarbitrary-modulusconvolutionmontgomery-multiplicationbarrett-reductionconstant-factortree-hashingtree-isomorphismanti-testrandomized-hashingtransform-lengthmodulus-choicepolynomial-multiplicationberlekamp-masseylinear-recurrencekitamasasequence-recovery+1+2+3+4

Learning Resources

OI Wiki, Number theoretic transform and its moduli

AtCoder Library, convolution documentation

OI Wiki, Berlekamp-Massey algorithm

cp-algorithms, Montgomery multiplication

Chess Programming Wiki, Zobrist hashing

OI Wiki, Tree hashing