A Simple Math Problem

Problem Description
Lele now is thinking about a simple function f(x).

If x < 10 f(x) = x.
If x >= 10 f(x) = a0 * f(x-1) + a1 * f(x-2) + a2 * f(x-3) + …… + a9 * f(x-10);
And ai(0<=i<=9) can only be 0 or 1 .

Now, I will give a0 ~ a9 and two positive integers k and m ,and could you help Lele to caculate f(k)%m.

Input
The problem contains mutiple test cases.Please process to the end of file.
In each case, there will be two lines.
In the first line , there are two positive integers k and m. ( k<2*10^9 , m < 10^5 )
In the second line , there are ten integers represent a0 ~ a9.

Output
For each case, output f(k) % m in one line.

Sample Input
10 9999
1 1 1 1 1 1 1 1 1 1
20 500
1 0 1 0 1 0 1 0 1 0

Sample Output
45
104

1个回答

 import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        printResult();
    }

    public static void printResult() {
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNextInt()) {
            int k = scanner.nextInt();
            int m = scanner.nextInt();
            int[] arr = new int[10];
            for(int i = 0; i < 10; i++)
                arr[i] = scanner.nextInt();
            System.out.println(getResult(arr, k) % m);
        }

    }

    public static int getResult(int[] a, int x) {
        if(x < 10)
            return x;
        ArrayList<Integer> list = new ArrayList<>();
        int result = 0;
        for(int i = 0; i <= x; i++) {
            if(i < 10)
                result = i;
            else {
                result = a[0]*list.get(i-1)+a[1]*list.get(i-2)+a[2]*list.get(i-3)+a[3]*list.get(i-4)+a[4]*list.get(i-5) +
                        a[5]*list.get(i-6)+a[6]*list.get(i-7)+a[7]*list.get(i-8)+a[8]*list.get(i-9)+a[9]*list.get(i-10);
            }
            list.add(result);
        }
        return list.get(x);
    }
}

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!