洛谷【P5004 专心OI - 跳房子】 题解
题目链接
https://www.luogu.org/problem/P5004
洛谷 P5004 专心OI - 跳房子
Imakf有一天参加了PINO 2017 PJ组,他突然看见最后一道题
他十分蒟蒻,写不出来
而如今他还是一个蒟蒻,他又看见一道题
他还是写不出来,于是便来请教您
题目描述
您有NN个格子,排成一行,从左往右编号为1,2,...,N1,2,...,N。您站在11号格子的左边,开始从左往右跳,跳到NN号格子右侧为止。由于您是一位成功的OIerOIer,您自然长得很胖,但您的力量也非常大!这使得您跳一次,当前格子到目标格子中间必须至少空出来MM格,但您可以跳无数格远!
您认为这么跳太没意思了,于是便想计算出有多少种方案可以跳完全程。由于方案可能过多,您会输出方案数量模(10^9+7)(109+7)的值
方案指经过格子编号的顺序不同,具体可见说明
题目简化一下……把NN个无色格子排成一行,可以把某些格子染成黑色,但两个黑色格子之间必须至少有MM个无色格子,求方案数
输入格式
第一行 N,MN,M
输出格式
跳完全程的方案模(10^9+7)(109+7)
一道高中的排列组合问题
原理:
考虑黑色格子最多的情况:最左侧是黑色,然后每隔M个格子都是黑色,这种情况下的黑色格子的总数为:(N-1)/(M+1)+1 这种排列情况最右侧的无色格子为(N-1)%(M+1),由于黑色格子间隔最少是M,并且此种情况所有黑色格子间隔都是M,所以黑色格子中间的格子是不能动的。现在把最右侧的无色格子看成是活动的,那么这些格子放置到任何位置都能满足要求,又因为(N-1)/(M+1)+1个黑色格子将N分割为了(N-1)/(M+1)+2个区域,所以黑色格子最多时的方案问题就转化为了高中的排列组合问题:(N-1)%(M+1)个小球放入(N-1)/(M+1)+2个盒子,小球相同,盒子不同,盒子里的小球可以为0。所以这种情况的方案数为C[((N-1)%(M+1)+(N-1)/(M+1)+1),(N-1)/(M+1)+1)。根据这种原理就可以求得所有的方案数了。代码如下:
#include<stdio.h> long long factorial(int m, int n)
{
int i,j;
long long ans = 1;
if(m < n-m) m = n-m;
for(i = m+1; i <= n; i++) ans *= i;
for(j = 1; j <= n - m; j++) ans /= j;
return ans;
}
int main()
{
int N,M,k,a,b,c=0;
long long d=0;
scanf("%d%d",&N,&M);
k=(N-1)/(M+1)+1;
a=(N-1)%(M+1);
for(b=k;b>1;b--)
{
d += factorial(b,a+c*(M+1)+b);
c++;
}
printf("%lld",(d+N+1)%1000000007);
return 0;
}
但是这个代码只能得10分,当N大的时候不行了,可以用快速阶乘解决
最新文章
- Mybatis 复习 Mybatis 配置 Mybatis项目结构
- php 读取文件
- sql 多行合一行
- Oracle建表脚本记录
- swift函数的用法,及其嵌套实例
- Python数据类型之列表
- collection的框架结构
- django中添加用户
- C#基础静态类的设计
- .net EF 事物 订单流水号的生成 (二):观察者模式、事物、EF
- SVN如何迁移到Git?
- Linux修改IP,DNS和网关
- msql索引
- CSRF &; CORS 的区别
- 重建整个数据库的索引(Server2000)
- java面试问题收集(2)
- openshift harp.js heroku react-router 4
- springmvc框架开发中解决产生的乱码情况
- Android:你不知道的 WebView 使用漏洞
- js-jquery-从SweetAlert到SweetAlert2
热门文章
- kendo ui - core
- 视觉光盘,只有我可以贴全世界唯一,Windows上最高级的DOCKER客户端数字, 夜晚点击一个都没有,值班的小编辛苦了
- java架构之路-(微服务专题)ribbon的基本使用和内部算法的自我实现
- sql 忘记密码 解决方法(window cmd命令解决)
- win10CPU版TensorFlow安装详细流程(踩N个坑之后的总结)
- web渗透步骤流程
- Linux设备中的UUID
- 自动化测试中,cookie的调用方法。
- ES6 - 基础学习(6): 对象扩展
- docker jenkins 前端node项目 自动化部署异常 env: ‘node’: No such file or directory