在杨辉三角中,从第一行第一列(0,0)开始,每次可选择向正下方走或向右下方走,走到第n行时不能超过第n行第k个元素,询问所经过路径的值的和的最小值mod(p),一共有T
组询问,T≤100000, 0≤k≤n≤1e9, 保证p是质数, 其中p<1e4
名字虽然是DP,但是可以找出最优方案。
优先考虑k≤2n的情况,先向下走n−k步到达(n−k−1,0)
再一路沿着右下方走,直到到达底部,即有Cn−k0+Cn−k+11+Cn−k+22+…+Cnk=Cn+1k
通过变换Cn−k0=Cn−k+10
再通过公式Cnm=Cn−1m+Cn−1m−1可将上述公式合并
得到Cn+1k
所以答案为Cn+1k+n−k
当k>2n时,根据对称性,令k=n−k即可转化成上一种情况
又发现题目涉及组合数取模,所以要用到费马小定理
费马小定理:
假如a是一个整数,p是一个质数,且gcd(a,p)=1,即a,p互质,那么有ap−1≡1(modp)
已知ap−1≡1,可以得到a⋅ap−2≡1,我们称a和ap−2为在mod(p)意义下的乘法逆元
然而这只解决了除法取模的问题,注意到n的范围在1e9直接计算组合数又是铁套老鹅(TLE),于是借助Lucas定理
对于质数p,有Cnm mod p=C⌊pn⌋⌊pm⌋⋅Cn mod pm mod p mod p
可知n mod p和m mod p一定是小于p的数,可直接求解,其余部分继续用Lucas定理求解,当m=0的时候返回1
1
2
3
4
|
long long Lucas(long long n, long long m, long long p) {
if (m == 0) return 1;
return (C(n % p, m % p, p) * Lucas(n / p, m / p, p)) % p;
}
|
有了这些工具之后就可以预处理阶乘和逆元了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
|
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <queue>
typedef long long LL;
const int MAXN = 10000;
using namespace std;
LL N,K,MOD;
bool isnotp[MAXN + 10];
LL pri[1500], num = 0;//素数表
int f[1300][MAXN];//阶乘
int inv[1300][MAXN];//逆元
inline void Euler() {
isnotp[1] = true;
memset(isnotp, false, sizeof(isnotp));
for (int i = 2; i <= MAXN; i++) {
if (!isnotp[i]) pri[++num] = i;
for (int j = 1; j <= num && i*pri[j] <= MAXN; j++) {
isnotp[i*pri[j]] = true;
if (i%pri[j]==0) break;
}
}
}
LL fffpow(LL x, LL y, LL pp) {
LL sum = 1;
LL a = x;
while (y) {
if (y&1) {
sum = (sum*a) % pp;
}
a = (a*a)%pp;
y>>=1;
}
return (sum)%pp;
}
int cnt = 0;
inline LL Lucas(int N,int M,int o)
{
LL a,b,ans=1;
while(N && M) {
a = N%pri[o];
b = M%pri[o];
if(a < b)return 0;
ans = ans*f[o][a]%pri[o]*inv[o][b]%pri[o]*inv[o][a-b]%pri[o];
N /= pri[o];
M /= pri[o];
}
return ans;
}
int main() {
Euler();
for(int i = 1; i <= num; i++) {
f[i][0] = f[i][1] = 1;
inv[i][0] = inv[i][1] = 1;
for(int j = 2;j < pri[i]; j++) {
f[i][j] = f[i][j-1]*j % pri[i];
inv[i][j] = fffpow(f[i][j], pri[i]-2, pri[i]);
}
}
while (cin >> N >> K >> MOD) {
LL ans;
if(K > N/2) K = N - K;
int l = 1, r = 1229;
while(l <= r) {
int mid = (l + r) >> 1;
if(MOD < pri[mid]) r = mid - 1;
else l = mid + 1;
}
ans = (Lucas(N + 1, K, l - 1) + N - K)%MOD;
printf("Case #%d: %lld\n", ++cnt, ans);
}
return 0;
}
|