【HDU】3944 - DP?（Lucas & 逆元 & 大组合数 & 打表）

FishWang

发布于 2025-08-26 15:01:19

3500

点击打开题目

DP?

Time Limit: 10000/3000 MS (Java/Others) Memory Limit: 128000/128000 K (Java/Others) Total Submission(s): 2934 Accepted Submission(s): 910

Problem Description

Figure 1 shows the Yang Hui Triangle. We number the row from top to bottom 0,1,2,…and the column from left to right 0,1,2,….If using C(n,k) represents the number of row n, column k. The Yang Hui Triangle has a regular pattern as follows. C(n,0)=C(n,n)=1 (n ≥ 0) C(n,k)=C(n-1,k-1)+C(n-1,k) (0<k<n) Write a program that calculates the minimum sum of numbers passed on a route that starts at the top and ends at row n, column k. Each step can go either straight down or diagonally down to the right like figure 2. As the answer may be very large, you only need to output the answer mod p which is a prime.

Input

Input to the problem will consists of series of up to 100000 data sets. For each data there is a line contains three integers n, k(0<=k<=n<10^9) p(p<10^4 and p is a prime) . Input is terminated by end-of-file.

Output

For every test case, you should output "Case #C: " first, where C indicates the case number and starts at 1.Then output the minimum sum mod p.

Sample Input

   1 1 2
4 2 7

Sample Output

   Case #1: 0
Case #2: 5

Author

phyxnj@UESTC

Source

2011 Multi-University Training Contest 11 - Host by UESTC

作孽啊第一次练习逆元，准备写完写个总结呢，上来就碰上这样一道题。

上来开开心心写了遍Lucas定理，TLE。

好的，既然数比较大，那我们打表，反正p是小于10000的素数，我们就把阶乘表逆元表打出来。

但是答案有个推倒：

答案是
c(n-k,0)+c(n-k+1,1)+c(n-k+2,2)+...+c(n-k+i,i)+...+c(n,k)+n-k
=c(n-k+1,0)+c(n-k+1,1)+c(n-k+2,2)+...+c(n-k+i,i)+...+c(n,k)+n-k
=c(n-k+2,1)+c(n-k+2,2)+...+c(n-k+i,i)+...+c(n,k)+n-k
=c(n-k+3,2)+...+c(n-k+i,i)+...+c(n,k)+n-k
=c(n-k+i,i-1)+...+c(n-k+i,i)+c(n,k)+n-k
=c(n,k-1)+c(n,k)+n-k
=c(n+1,k)+n-k

然后套用就行了。

让我郁闷的是，不知道为啥，注释掉的那部分那么去求逆元就会wa，但是感觉原理上一样啊，求教大神QAQ

代码如下；

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define CLR(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define LL long long
LL fac[10005][10005];
LL prime[1300];		//10000之内的素数不到 1300个 
LL inv[10005][10005];		//阶乘逆元 
int ant = 0;		//素数个数 
bool su[10011] = {1,1};
void getprime()		//求出所有素数 
{
	for (int i = 2 ; i <= 10000 ; i++)
	{
		if (su[i])
			continue;
		prime[ant++] = i;
		for (int j = i + i ; j <= 10000 ; j += i)
			su[j] = true;
	}
}
LL quick_mod(LL n , LL m , LL mod)		//快速幂 
{
	LL ans = 1;
	n %= mod;
	while (m)
	{
		if (m & 1)
			ans = (ans * n) % mod;
		n = n * n % mod;
		m >>= 1;
	}
	return ans;
}
void getfac()		//预处理阶乘表 
{
    for(int i = 0 ; i < ant ; i++)
    {
        fac[prime[i]][0] = inv[prime[i]][0] = 1;
        for(int j = 1 ; j < prime[i] ; j++)
        {
            fac[prime[i]][j] = (fac[prime[i]][j-1] * j) % prime[i];
            inv[prime[i]][j] = quick_mod(fac[prime[i]][j] , prime[i] - 2 , prime[i]);
        }
    }
}
LL C(LL n , LL k , LL mod)		//求组合数
{
	if (k > n)
		return 0;
	else if (n == k)
		return 1;
	else
		return fac[mod][n] * (inv[mod][k] * inv[mod][n-k] % mod) % mod;
//		return fac[mod][n] * (inv[mod][fac[mod][k] * fac[mod][n-k] % mod]) % mod;		//实在是想不通这样求逆元错在哪里 
}
LL Lucas(LL n , LL k , LL mod)		//递归实现Lucas定理 
{
	if (k == 0)		//递归终止条件 
		return 1;
	else
		return C(n % mod , k % mod , mod) * Lucas(n / mod , k / mod , mod) % mod;
}
int main()
{
	LL mod;
	getprime();		//预处理素数表 
	getfac();		//预处理阶乘表 
	int Case = 1;
	LL n,k;
	while (~scanf ("%lld %lld %lld",&n,&k,&mod))
	{
		printf ("Case #%d: ",Case++);
		if (2*k > n)
			k = n-k;
		printf ("%lld\n",(Lucas(n+1 , k , mod) + n - k) % mod);
	}
	return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-08-26，如有侵权请联系 cloudcommunity@tencent.com 删除

递归