（递归）P1192 台阶问题

题解：

这其实是变相的斐波那契，观察下列等式：

//k=2 : 1 2 3 5 8  13 21 34......

//k=3 : 1 2 4 7 13 24 44 81...

//k=4 : 1 2 4 8 15 29 56 108...

//k=5 : 1 2 4 8 16 31 61 120...

我们不难发现当n<=k时第N项=(上一项*2)%100003,当n>k时第N项=（上一项*2-第n-1-k项）%100003; 所以递推式就是f(x)=x<=n?f(x-1)*2:f(x-1)*2-f(x-1-k);

#include<iostream>
using namespace std;

int main()
{
int N,K;
cin>>N>>K;

int f[N+1]={0};
f[1]=1,f[0]=1;
int i=2;
while(i<=N){
  if(i<=K){
   f[i]=f[i-1]*2%100003;
  }else{
   f[i]=(f[i-1]*2-f[i-1-K]+100003/*防止负数产生，我因为他WA了一次*/)%100003; //这里要小心负数的出现
  }
  i++;
}
cout<<f[N]<<endl;
return 0;
}

巴特西

（递归）P1192 台阶问题

最新文章

热门文章