hdu 3944 数学组合+帕斯卡定理_黑码的博客-程序员宝宝

技术标签: 组合数学  

这里写图片描述

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)
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

这里写图片描述

(1)先走最外侧的斜边,然后竖直向下走到达c(n,m)
那么我们会走过m+1个1
然后还需要加入c(m+1,m)+c(m+2,m)+c(m+3,m)+…+c(n,m)
然后我先强行加入c(m+1,m+1),然后可以将c(m+1,m)和c(m+1,m+1)合并成c(m+2,m+1),然后不断向后合并,最终得到c(n+1,m+1),因为我们加入了c(m+1,m+1)=1所以最终的答案是c(n+1,m+1)+m
(2)先竖直向下,然后走斜边
那么我们会先走过n-m个1
然后还需要加入c(m,0)+c(m+1,1)+c(m+2,2)+…+c(n,m)
c(m,0)=c(m+1,0)替换,然后将c(m+1,0),c(m+1,1)合并得到c(m+2,1),然后不断向后合并最终得到c(n+1,m)
所以最终的答案是c(n+1,m)+n-m
然后观察后发现,单独的1的个数多的方案最终的结果会更优。
所以当n-m>m,选择方案(2),否则选择方案(1)

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn=10005;
int prime[maxn];
int C[maxn][maxn];
int A[maxn][maxn];
vector<int> v;

int qpow(int a,int b,int m)
{
    int ans=1;
    a%=m;
    while(b)
    {
        if(b&1){
            ans=ans*a%m;
        }
        b>>=1;
        a=a*a%m;
    }
    return ans;
}

void init()
{
    for(int i=2;i<maxn;i++)
    {
        if(!prime[i])
        {
        v.push_back(i);
        for(int j=i*2;j<maxn;j+=i)
        {
            prime[j]=1;
        }
        }
    }
    int size=v.size();
    for(int i=0;i<size;i++)
    {
        A[v[i]][0]=C[v[i]][0]=1;
        for(int j=1;j<v[i];j++)
            A[v[i]][j]=(A[v[i]][j-1]*j)%v[i];
        C[v[i]][v[i]-1]=qpow(A[v[i]][v[i]-1],v[i]-2,v[i]);
        for(int j=v[i]-2;j>=0;j--)
        {
            C[v[i]][j]=(C[v[i]][j+1]*(j+1))%v[i];
        }
    }
}

int com(int n,int m,int P)
{
    return A[P][n]*(C[P][m]*C[P][n-m]%P)%P;
}

int Lucas(int n,int m,int P)
{
    if(m==0) return 1;
    return com(n%P,m%P,P)*Lucas(n/P,m/P,P)%P;
}

int main()
{
    int n,m,p;
    int cas=1;
    init();
    while(cin>>n>>m>>p)
    {
        if(2*m<n)
        printf("Case #%d: %d\n",cas++,(Lucas(n+1,m,p)+n-m)%p );
        else
        printf("Case #%d: %d\n",cas++,(Lucas(n+1,m+1,p)+m)%p ); 
    }
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Littlewhite520/article/details/71774390

智能推荐

Kindeditor and cKediter for Ruby on Rails_weixin_34124651的博客-程序员宝宝

为什么80%的码农都做不了架构师?&gt;&gt;&gt; ...

hdu1052 Tian Ji -- The Horse Racing (贪心)_田益铭的博客-程序员宝宝

转载请注明出处:http://blog.csdn.net/u012860063题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1052Tian Ji -- The Horse RacingTime Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/32768 K (Jav...

手把手教你用Centos7安装完全分布式Hadoop3.2.1_liemozhu的博客-程序员宝宝

一、设置ssh免密码登录1.确认ssh服务已经安装并打开:2.打开文件/etc/ssh/sshd_config,确保以下配置已经添加(如果被"#“注释了就把”#"删除,用sudo完成):AuthorizedKeysFile .ssh/authorized_keysPubkeyAuthentication yes3、输入ssh-keygen -t rsa,然后一路回车,...

PDF.js在前后端<iframe>标签中在线预览PDF文件的使用心得_lwl827的博客-程序员宝宝_jsp预览pdf

前端时间项目中需要在前后端预览PDF文件(后端使用jsp,前端H5),因为页面中还包含点赞,分享等功能,所以考虑用&lt;iframe&gt;标签来打开PDF文件进行预览,之前没有做过所以花了点时间研究了一下,现在记录一下,希望能够帮到有需要的朋友。(PDF.js可以在网上搜索自行下载,具体怎样使用PDF.js请自行搜索,这里不多讲)1、后台jsp的使用 项目中的PDF文件是上传到百度云的所以在上传和下载的时候依赖的这个包,上传后将路径保存在content字段中。 后台读...

vux 地图插件_基于vue的移动端组件vux的安装及使用_可没就是说的博客-程序员宝宝

一、安装&lt;1&gt;. 在项目里安装vuxnpm install vux --save&lt;2&gt;. 安装vux-loader (这个vux文档似乎没介绍,当初没安装结果报了一堆错误)npm install vux-loader --save-dev&lt;3&gt;. 安装less-loader (这个是用以正确编译less源码,否则会出现 ' Cannot GET / ')npm...

008-Python3.x 标准模块库目录_sonehb的博客-程序员宝宝

文章目录Python3.x 标准模块库目录1、文本2、二进制数据3、数据类型4、数学5、函数式编程6、文件与目录7、持久化8、压缩9、文件格式化10、加密11、操作系统工具12、并发13、进程间通信14、互联网15、HTML与XML16、互联网协议与支持17、多媒体18、国际化19、编程框架20、Tk图形用户接口21、开发工具22、调试23、运行时24、解释器25、导入模块26、Python语言2...

随便推点

将一个字符串str的内容颠倒过来,并输出。str的长度不超过100个字符。 如:输入“I am a student”,输出“tneduts a ma I”。_小猴子0831的博客-程序员宝宝

/*** 题目描述将一个字符串str的内容颠倒过来,并输出。str的长度不超过100个字符。 如:输入“I am a student”,输出“tneduts a ma I”。输入参数:inputString:输入的字符串返回值:输出转换好的逆序字符串*/package com.niukewang.huawei.string;import java.util.Scanner;public class MainFour { /* * 将字符串分隔成字...

Unable to find a javac compiler;Perhaps JAVA_HOME does not point to the JDK_孤独侠客123的博客-程序员宝宝

tomcat下如何配置jsp、servlet,经产遇到环境配置问题,例如:type Exception reportmessage description The server encountered an internal error () that prevented it from fulfilling this request.exception org.apache.jasper.Jas

FLASH优化_iteye_20805的博客-程序员宝宝

•优化显示:透明效果,滤镜,缩放以及旋转可以产生分成绚丽的效果,但是这些效果同时也吃掉了很多的CPU,所以在游戏中尽可能用位图代替这些效果。•流畅的逻辑运算:另外一个瓶颈是游戏中的逻辑判断。尽量减少不必要的判断,取消程序中的那些临界近似值的判断。出来显示问题,优化逻辑判断是提高游戏性能最为显著的一个。•使用Vector类存储一组相同类型的数据:Flash player10引...

Unity 5: 2D Movement in an RPG Game Unity 5:RPG游戏中的2D运动 Lynda课程中文字幕_Lynda中文网的博客-程序员宝宝

Unity 5: 2D Movement in an RPG Game 中文字幕Unity 5:RPG游戏中的2D运动 中文字幕Unity 5: 2D Movement in an RPG Game了解如何在基于图块的2D地图上移动玩家,并使用该移动触发事件 - 创建类似于经典RPG游戏体验在本课程中,Jesse Freeman在Unity 5 2D:随机地图生成中学到的经验教训:增加一名玩...

员工管理数据库设计_VictorHan01的博客-程序员宝宝_员工管理系统数据库设计

一、课题背景和目的员工管理数据库系统,有助于为对员工数量增多,信息量增大,以及员工部门分配,工资发放等问题实现现代、化网络化管理,能够提高企业管理效率,提高准确度,节约企业成本,提高生产效率。通过该课题可以熟悉PowerDesigner设计数据库的流程,巩固数据库的设计规则和设计原理,以及对数据库进行多种逻辑查询。二、数据库的需求分析通过设计数据库实现对企业员工的基本信息、职...

推荐文章

热门文章

相关标签