P1192 台阶问题 题解

· · 题解

P1192 台阶问题 题解

都在代码里

Ps:请不要复制粘贴QwQ 
#include <cstdio>//知识涉及:同余 递归 记忆化搜索
#define mod 100003
int dp[1000010];
int f(int n,int k){
dp[1] = dp[0] = 1;
for(int i = 2;i <= n;i++){
if(i <= k) dp[i] = (dp[i-1]*2)%mod;//同余
else dp[i] = (dp[i-1]*2 - dp[i-k-1]) % mod;
}
return (dp[n]+mod)%mod;//防止负数 -- 同余 
}
int main(){
int n,k;
scanf("%d%d",&n,&k);
printf("%d",f(n,k));
return 0;
} 
/*f函数公式的推导:
dp[x] = dp[x-1]+dp[x-2]+...+dp[x-k]
dp[x-1] = dp[x-2]+dp[x-3]+...+dp[x-k-1]
我们发现,变成了公差为2的等差数列
所以 在x<=k时:dp[x] = (2*dp[x-1])%mod
若x > k:
dp[x] = dp[x-1]*2-dp[x-k-1]
dp[x-k-1] --> 首项
因为若x<=k时 x-k-1<=0 
*/