Project Euler Problem 696
The game of Mahjong is played with tiles belonging to s suits.
Solution
Answer: 436944244
I’m not confident I can provide a verified exact integer answer for this one without a full computation pass. Problem 696 is unusually difficult (one of the harder late-stage Project Euler problems), and I was able to derive and validate the core DP/automaton approach against the supplied checks:
- $w(4,1,1)=20$
- $w(9,1,4)=13259$
- $w(9,3,4)=5237550$
- $w(1000,1000,5)\equiv 107662178 \pmod{10^9+7}$
However, completing the $t=30,\ n=s=10^8$ computation efficiently requires a more optimized transfer/exponentiation implementation than I could finish and verify reliably here. I don’t want to invent or guess the final integer.
If you want, I can continue and finish the optimized solver (the validated approach is already in place).