DP? 素数筛+Lucas定理+费马小定理

Description

在杨辉三角中,从第一行第一列(0,0)(0,0)开始,每次可选择向正下方走或向右下方走,走到第nn行时不能超过第nn行第kk个元素,询问所经过路径的值的和的最小值mod(p)mod(p),一共有T组询问,T100000T \leq 1000000kn1e90 \leq k \leq n \leq 1e9, 保证pp是质数, 其中p<1e4p < 1e4

Solution

名字虽然是DP,但是可以找出最优方案。 优先考虑kn2k \leq \frac{n}{2}的情况,先向下走nkn-k步到达(nk1,0)(n-k-1,0) 再一路沿着右下方走,直到到达底部,即有Cnk0+Cnk+11+Cnk+22++Cnk=Cn+1kC_{n-k}^{0}+C_{n-k+1}^{1}+C_{n-k+2}^{2}+…+C_{n}^{k}=C_{n+1}^{k} 通过变换Cnk0=Cnk+10C_{n-k}^{0} = C_{n-k+1}{0} 再通过公式Cnm=Cn1m+Cn1m1C_{n}^{m}=C_{n-1}^{m}+C_{n-1}^{m-1}可将上述公式合并 得到Cn+1kC_{n+1}^{k} 所以答案为Cn+1k+nkC_{n+1}^{k}+n-kk>n2k > \frac{n}{2}时,根据对称性,令k=nkk=n-k即可转化成上一种情况 又发现题目涉及组合数取模,所以要用到费马小定理

费马小定理: 假如aa是一个整数,pp是一个质数,且gcd(a,p)=1gcd(a,p)=1,即a,pa,p互质,那么有ap11(modp)a^{p−1}≡1(modp)

已知ap11a^{p-1}≡1,可以得到aap21a \cdot a^{p-2}≡1,我们称aaap2a^{p-2}为在mod(p)mod(p)意义下的乘法逆元 然而这只解决了除法取模的问题,注意到nn的范围在1e91e9直接计算组合数又是铁套老鹅(TLE),于是借助Lucas定理

对于质数pp,有Cnm mod p=CnpmpCn mod pm mod p mod pC_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 pn\ mod\ pm mod pm\ mod\ p一定是小于pp的数,可直接求解,其余部分继续用Lucas定理求解,当m=0m=0的时候返回11

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;
}
0%