枚举 $j \in P \cup \{4\}$ 加威尔逊定理。只会单组数据不会多测。。
by huazai676 @ 2024-04-22 01:29:40
@[masonpop](/user/614725)
$$C(i,j)=\tbinom{j}{i}(j-1)! $$
将乘法分开，分别计算。
右边是威尔逊定理：
$j$ 是非 $4$ 合数时，$(j-1)!\equiv0\pmod j$。
$j$ 是 $4$ 时 $(j-1)!\equiv2\pmod j$。
$j$ 是质数时 $(j-1)!\equiv j-1 \pmod j$
左边卢卡斯定理。
$$\tbinom{i}{j}\equiv\tbinom{i\bmod p}{j\bmod p}\tbinom{i/p}{j/p}$$
左边显然是很好计算的，右边只有质数和 $4$ 有贡献。
by yshpdyt @ 2024-04-22 08:25:01
@[yshpdyt](/user/229008) 懂了，感谢！
by masonpop @ 2024-04-22 08:29:51