洛谷P1192台阶问题
2024-09-05 13:54:34
题目描述
有NN级的台阶,你一开始在底部,每次可以向上迈最多KK级台阶(最少11级),问到达第NN级台阶有多少种不同方式。
输入格式
两个正整数N,K。
输出格式
一个正整数,为不同方式数,由于答案可能很大,你需要输出ans \bmod 100003ansmod100003后的结果。
输入输出样例
输入 5 2
输出 8
说明/提示
对于20\%20%的数据,有N ≤ 10, K ≤ 3N≤10,K≤3;
对于40\%40%的数据,有N ≤ 1000N≤1000;
对于100\%100%的数据,有N ≤ 100000,K ≤ 100N≤100000,K≤100。
#include<bits/stdc++.h>
const int mod=;
const int N = 1e6+;
int a[N],n,k;
using namespace std;
int main()
{
cin>>n>>k;
a[]=a[]=;
for(int i = ;i<=n;++i){
if(i<=k)a[i]=a[i-]*%mod;
else a[i]=a[i-]*-a[i-k-],a[i]%=mod;
}
cout<<(a[n]+mod)%mod<<endl;
return ;
}
AC代码
第一篇题解写的代码无敌简单orz,困得要死水了一题,但是公式好像一时半会还解释不清楚orz
后面几个方法复杂了一点点然后看到了用矩阵求斐波那契数列的博客,,我好菜啊一直在补早就该学会的东西
最新文章
- 浅谈Extjs radiogroup change事件与items下的checked属性
- ASP.NET MVC 学习笔记(一)
- :nth-child()和:nth-of-type(n)区别
- 六个超大规模Hadoop(前景)
- Enter password: ERROR 2002 (HY000): Can&#39;t connect to local MySQL server through socket &#39;/var/lib/mysql/mysql.sock&#39; (2)
- iOS核心笔记—源代码管理工具-SVN
- Swashbuckle.AspNetCore3.0的二次封装与使用
- 七、Android动画
- 网页布局中页面内容不足一屏时页脚footer固定底部
- mininet的学习之一
- HSSFWorkbook操作excel读写
- SpringBoot整合dubbo
- react-native获取设备信息app版本信息,react-native-device-info
- NOIP2018 货币系统
- Revit API移动风管
- 使用 TXT 文本存储
- python第二十二课——list函数
- 自定义ProgressBar的加载效果
- BZOJ 3130: [Sdoi2013]费用流 网络流 二分 最大流
- 嵌入式设备hacking(转)