UIC-ACM 新春挑战赛
A
Source: HDU 4767 Bell
打了个暴力发现输出不对，发现这个模数不是一个质数
50 分做法就是直接的结合杨辉三角暴力 O(n^2) 递推
听讲题发现 linux 下面有个很赛艇的 prompt 可以直接分解质因数：factor 95041567
然后你就会发现 95041567 = 31 * 37 * 41 * 43 * 47
然后题目里面给了一个公式 B[p + n] = B[n] + B[n + 1] (mod p and p is a prime)
类似于 Fibonacci 数列的递推，常系数齐次线性递推 构造转移矩阵。这样就可以对于单个质因数推出答案。
现在的问题是对于多个质因数的答案如何合并？中国剩余定理。
1 |
B
1 |
C
1 |
D
1 |
UIC-ACM 新春挑战赛