快手[编程题]魔法深渊

输入共有M行，(1<=M<=1000)

第一行输入一个数M表示有多少组测试数据，

接着有M行，每一行都输入一个N表示深渊的台阶数

输出可能的爬出深渊的方式

4
1
2
3
4

1
2
3
6

为了防止溢出，可将输出对10^9 + 3取模

import java.util.Scanner;
public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] sc = new int[n];
        for(int i=0;i<n;i++){
            sc[i]=in.nextInt();
        }
        int[] dp=new int[1001];
        for(int i=1;i<1001;i++){
            dp[i]=0;
        }
        dp[0]=1;
        int[] byteArray={1, 2, 4, 8, 16, 32, 64, 128, 256, 512};
        for(int i=0;i<1000;i++){
            for(int j=0;j<10 && i>= byteArray[j];j++){
                dp[i]+=dp[i-byteArray[j]];
                dp[i]%=(1000000000 + 3);
            }
        }
        for(int i=0;i<n;i++){
            System.out.println(dp[sc[i]]);
        }
        in.close();
    }
}