Description
在杨辉三角中，从第一行第一列$(0,0)$开始，每次可选择向正下方走或向右下方走，走到第$n$行时不能超过第$n$行第$k$个元素，询问所经过路径的值的和的最小值$mod(p)$，一共有T组询问，$T \leq 100000$， $0 \leq k \leq n \leq 1e9$, 保证$p$是质数， 其中$p < 1e4$
Solution
名字虽然是DP，但是可以找出最优方案。
优先考虑$k \leq \frac{n}{2}$的情况，先向下走$n-k$步到达$(n-k-1,0)$
再一路沿着右下方走，直到到达底部，即有$C_{n-k}^{0}+C_{n-k+1}^{1}+C_{n-k+2}^{2}+…+C_{n}^{k}=C_{n+1}^{k}$
通过变换$C_{n-k}^{0} = C_{n-k+1}{0}$
再通过公式$C_{n}^{m}=C_{n-1}^{m}+C_{n-1}^{m-1}$可将上述公式合并
得到$C_{n+1}^{k}$
所以答案为$C_{n+1}^{k}+n-k$
当$k > \frac{n}{2}$时，根据对称性，令$k=n-k$即可转化成上一种情况
又发现题目涉及组合数取模，所以要用到费马小定理
费马小定理:
假如$a$是一个整数，$p$是一个质数，且$gcd(a,p)=1$，即$a,p$互质，那么有$a^{p−1}≡1(modp)$
已知$a^{p-1}≡1$，可以得到$a \cdot a^{p-2}≡1$，我们称$a$和$a^{p-2}$为在$mod(p)$意义下的乘法逆元
然而这只解决了除法取模的问题，注意到$n$的范围在$1e9$直接计算组合数又是铁套老鹅(TLE)，于是借助Lucas定理
对于质数$p$,有$C_n^m\ mod \ p = C_{\lfloor \frac{n}{p} \rfloor}^{\lfloor \frac{m}{p} \rfloor} \cdot C_{n\ mod\ p}^{m\ 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;
}
|
有了这些工具之后就可以预处理阶乘和逆元了
Code
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;
}
|
Zhiwei Zhang
included in Algorithm