网站信息内容建设管理,我要自学网app,网站开发必须要做前端吗,抢注qq空间专属域名网站题目描述
前几个月放映的头号玩家简直火得不能再火了#xff0c;作为一个探索终极AI的研究人员#xff0c;月神自然去看了此神剧。
由于太过兴奋#xff0c;晚上月神做了一个奇怪的梦#xff0c;月神梦见自己掉入了一个被施放了魔法的深渊#xff0c;月神想要爬上此深渊…题目描述
前几个月放映的头号玩家简直火得不能再火了作为一个探索终极AI的研究人员月神自然去看了此神剧。
由于太过兴奋晚上月神做了一个奇怪的梦月神梦见自己掉入了一个被施放了魔法的深渊月神想要爬上此深渊。 已知深渊有N层台阶构成1 N 1000)并且每次月神仅可往上爬2的整数次幂个台阶(1、2、4、....)请你编程告诉月神月神有多少种方法爬出深渊
输入描述:
输入共有M行(1M1000)第一行输入一个数M表示有多少组测试数据接着有M行每一行都输入一个N表示深渊的台阶数
输出描述:
输出可能的爬出深渊的方式
示例1
输入
复制
4
1
2
3
4
输出
复制
1
2
3
6
备注:
为了防止溢出可将输出对10^9 3取模
如果台阶数为4每一步可以爬12,4,个台阶则dp[4]dp[3]dp[2]dp[0]
同理有dp[n]dp[n-1]dp[n-2]dp[n-4]......
一、递归的方法但是本题递归在提交时会超时因此需采用第二种非递归的方法
#includestdio.h #includemath.h int Mod1000000003; int Fun(int n) { int i0,sum0,t,x; if(n1) { return 1; } if(n0) { return 1; } if (n 2) { return 2; } while(1) { tpow(2,i); if(n-t0) { break; } sumFun(n-t); sum%1000000003; i; } return sum; } int main() { int n,t,i,N; scanf(%d,N); int a[N]; for(i0;iN;i) { scanf(%d,n); a[i]Fun(n); } for(i0;iN;i) { printf(%d\n,a[i]); } }
二、非递归
#includestdio.h #includemath.h int Mod1000000003; int main() { int n,t,i; int dp[1000],j; dp[0]1; dp[1]1; for(i2;i1000;i) { dp[i]0; for(j1;ji;j*2) { dp[i]dp[i-j]; dp[i]%Mod; } } int N; scanf(%d,N); int a[N]; for(i0;iN;i) { scanf(%d,n); a[i]dp[n]; } for(i0;iN;i) { printf(%d\n,a[i]); } }
