P1192 台阶问题

P1192 台阶问题题目描述有NNN级台阶你一开始在底部每次可以向上迈1∼K1\sim K1∼K级台阶问到达第NNN级台阶有多少种不同方式。问题很简单主要记录几种思路。同时答案不要忘记 mod100003思路一递归最暴力的一种数据再大一点就会炸。intfind(intx,intk){if(a[x])returna[x];intsum0;//不要忘记初始化for(inti1;ikx-i0;i){find(x-i,k);suma[x-i]%100003;}a[x]sum%100003;returna[x];}intmain(){intn,k;cinnk;a[0]1,a[1]1;coutfind(n,k);return0;}思路二递推也有两种递推。递推一直接往上双重循环枚举。ans[0]1;for(inti1;in;i){for(intj1;jki-j0;j){ans[i]ans[i-j];ans[i]%100003;}}递推二注意到存在通式对于一个小于等于k的数x而言ans[x]ans[x-1]*2对于一个大于k的数而言ans[x]ans[x-1]*2-ans[x-k-1]。需要手写推导一下。#definemod100003for(inti2;in;i){if(ik)ans[i]ans[i-1]*2;elseans[i]ans[i-1]*2-ans[i-k-1];ans[i]%mod;}intx(ans[n]mod)%mod;coutx;这里需要注意一下的就是因为过程中不断取余导致原有的大小被改变会导致出现负数的情况结尾需要100003抵消一下。到此AC (´ω)