HDOJ 3944 DP?
2024-10-20 04:52:57
尽量沿着边走距离最短。化减后 C(n+1,k)+ n - k,
预处理阶乘,Lucas定理组合数取模
DP?
Time Limit: 10000/3000 MS (Java/Others) Memory Limit: 128000/128000 K (Java/Others)
Total Submission(s): 1899 Accepted Submission(s): 633
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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm> using namespace std; typedef long long int LL; LL n,k,p; LL fact[1300][11000]; LL QuickPow(LL x,LL t,LL m)
{
if(t==0) return 1LL;
LL e=x,ret=1LL;
while(t)
{
if(t&1LL) ret=(ret*e)%m;
e=(e*e)%m;
t>>=1LL;
}
return ret%m;
} int prime[2000],pr;
bool vis[10100]; void get_prime()
{
for(int i=2;i<10100;i++)
{
if(vis[i]==false)
prime[pr++]=i;
for(int j=2*i;j<10100;j+=i)
vis[j]=true;
}
} void get_fact()
{
for(int i=0;i<1240;i++)
{
fact[i][0]=1LL;
for(int j=1;j<=prime[i]+10;j++)
{
fact[i][j]=(fact[i][j-1]*j)%prime[i];
}
}
} LL Lucas(LL n,LL m,LL p)
{
LL ret=1LL;
int id=lower_bound(prime,prime+pr,p)-prime;
while(n&&m)
{
LL a=n%p,b=m%p;
if(a<b) return 0;
ret=(ret*fact[id][a]*QuickPow((fact[id][b]*fact[id][a-b])%p,p-2,p)%p)%p;
n/=p; m/=p;
}
return ret%p;
} int main()
{
get_prime();
get_fact();
int cas=1;
while(scanf("%I64d%I64d%I64d",&n,&k,&p)!=EOF)
{
if(k>n/2) k=n-k;
LL ans=(Lucas(n+1,k,p)+n-k)%p;
printf("Case #%d: %I64d\n",cas++,ans);
}
return 0;
}
最新文章
- spring+junit单元测试
- RHEL7挂载ISO做本地yum
- .NET异步编程之回调
- [安卓] 9、线程、VIEW、消息实现从TCP服务器获取数据动态加载显示
- Hadoop入门经典:WordCount
- 自定义Session类实现
- Postgresql命令行和数据库备份与恢复
- 深入浅出ES6(十四):let和const
- IIS 允许无后缀文件访问的配置
- Linux 系统下查看硬件信息命令大全
- 【Android 应用开发】Android中使用ViewPager制作广告栏效果 - 解决ViewPager占满全屏页面适配问题
- 反素数ant HYSBZ - 1053(数学+dfs)
- 一、python中的一切皆对象
- [转]Laravel 数据库实例教程 —— 使用查询构建器实现对数据库的高级查询
- Java&#160;Spring&#160;cron表达式使用详解
- 20190318wdVBA_替换下划线
- 微信小程序中用setData修改一个对象的属性值
- 搭建FTP服务器 window7
- BZOJ4813或洛谷3698 [CQOI2017]小Q的棋盘
- Java IO流杂谈