因為新數列中的數線性無關，即我們随意組合不會有重複結果，是以答案就是C(n, k) % p，因為p比較小，寫個擴充Lucas就好了。
證明一下線性無關：
首先有兩個引理：
定理1：一個n×n的矩陣A是非奇異的充要條件為 A的行列式不等于0。
定理2：令x1, x2, ..., xn為R^n中的n個向量，并令X = (x1, ...,xn)。向量x1,x2, ...,xn線性無關的充要條件是X為非奇異的。
是以我們隻需要計算這個行列式的值，如果結果不為0，那麼就是線性無關的。
我們把每個數都寫成二進制的形式，把二進制的每一位都看成一維。
比如6 = 110(2)，那麼這個向量就是（1，1，0）。
舉個例子，我們證明1，2，4是線性無關的，首先我們寫出向量，分别為
（0，0，1），（0，1，0），（1，0，0）
得到行列式：
（注意這裡是二進制的行列式。把加減法看做異或，把乘法看做與。）
上式不等于0，說明是線性無關的。
我們現在要證明新的數列1，3，5，10，17，39...是線性無關的，那麼我們把新的數清單示為行列式。
表示成的行列式一定為這種形式：
（注意這裡是二進制的行列式。把加減法看做異或，把乘法看做與。）
它的行列式等于1，說明新數列線性無關。
Q：為什麼反對角線上都是1？
A：考慮原數列的行列式，反對角線上都是1。每個數與它的約數位置異或，這個約數位置的數的二進制長度比這個數要短，無論怎麼異或都不會改變這個1。
Q：為什麼這個行列式等于-1？
A：因為隻有反對角線上沒有0。
Q：為什麼有x。。
A：因為異或後的結果我也不知道是0是1呀...
Q.E.D.
直接上模闆即可。
#include <cstdio>
typedef unsigned long long ULL;
typedef long long LL;
inline void exgcd(ULL a, ULL b, LL &x, LL &y) {
b ? (exgcd(b, a % b, y, x), y -= a / b * x) : (x = 1, y = 0);
}
inline ULL qpow(ULL x, ULL n, ULL p) {
ULL ans = 1;
for(ULL t = x; n; n >>= 1, t = x * x % p) if(n & 1) ans = ans * t % p;
return ans;
}
inline ULL c1(ULL n, ULL p, ULL pk) {
if(n == 0) return 1;
ULL ans = 1;
for(ULL i = 2; i <= pk; i++) if(i % p) ans = ans * i % pk;
ans = qpow(ans, n / pk, pk);
for(ULL k = n % pk, i = 2; i <= k; i++) if(i % p) ans = ans * i % pk;
return ans * c1(n / p, p, pk) % pk;
}
inline ULL inv(ULL a, ULL m) {
LL x, y;
exgcd(a, m, x, y);
if(x < 0) x += m;
return x;
}
inline ULL calc(ULL n, ULL m, ULL p, ULL pi, ULL pk) {
ULL a = c1(n, pi, pk), b = c1(m, pi, pk), c = c1(n - m, pi, pk), k = 0;
for(ULL i = n; i; i /= pi) k += i / pi;
for(ULL i = m; i; i /= pi) k -= i / pi;
for(ULL i = n - m; i; i /= pi) k -= i / pi;
ULL ans = a * inv(b, pk) % pk * inv(c, pk) % pk * qpow(pi, k, pk) % pk;
return ans * (p / pk) % p * inv(p / pk, pk) % p;
}
int main() {
ULL n, m, p;
scanf("%llu%llu%llu", &n, &m, &p);
ULL ans = 0;
for(ULL i = 2, x = p; x > 1; i++) if(x % i == 0) {
ULL k;
for(k = 1; x % i == 0; x /= i) k *= i;
ans = (ans + calc(n, m, p, i, k)) % p;
}
printf("%llu\n", ans);
return 0;
}