Cerinta completa

We call a sequence of N natural numbers (a1, a2, …, aN) a P-sequence, if the product of any two adjacent numbers in it is not greater than P. In other words, if a sequence (a1, a2, …, aN) is a P-sequence, then ai * ai+1 ≤ P ∀ 1 ≤ i < N

You are given N and P. Your task is to find the number of such P-sequences of N integers modulo 109+7.

Input Format

The first line of input consists of N
The second line of the input consists of P.

Constraints

2 ≤ N ≤ 103
1 ≤ P ≤ 109
1 ≤ ai

Output Format

Output the number of P-sequences of N integers modulo 109+7.

Sample Input 0

2
2

Sample Output 0

3

Explanation 0

3 such sequences are {1,1},{1,2} and {2,1}

Limbajul de programare folosit: java8

Cod:

//Week 1, Wednesday
//https://www.hackerrank.com/contests/w1/challenges/p-sequences
import java.io.*;
import java.util.*;

public class Solution {
    
    public final static int MOD = 1000000007;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        short N = Short.parseShort(br.readLine());
        int P = Integer.parseInt(br.readLine());
        
        //Create list
        List<Integer> list = new ArrayList<Integer>();
        
        //Initialize list
        int dividend = P;
        int divisor = 1;
        int quotient = P;
        list.add(quotient);
        while (divisor < quotient){
            ++divisor;
            quotient = dividend / divisor;
            list.add(quotient);
        }
        while (--divisor > 0){
            list.add(divisor);
        }

        int length = list.size();

        //Create and initialize sums array
        int[] sums = new int[length+2];
        int i = 0;
        for(int v : list){
            sums[++i] = v;
        }
        list = null;

        //Create and initialize mults array
        int[] mults = new int[length+2];
        i = length;
        for(int j = 1; j <= length; ++j){
            mults[i--] = sums[j] - sums[j+1];
        }
        
        //Solve
        boolean isOdd = (--N & 1) == 1;
        N >>= 1;
        while (N-- > 0){
            for(i = 1; i <= length; ++i){
                sums[i] = (int)((((long)sums[i]) * mults[i]) % MOD);
                sums[i] = (sums[i] + sums[i-1]) % MOD;
            }
            i = length;
            for(int j = 0; i > 0; --i){
                sums[i] = (int)((((long)sums[i]) * mults[++j]) % MOD);
                sums[i] = (sums[i] + sums[i+1]) % MOD;
            }
        }
        if (isOdd){
            for(i = 1; i <= length; ++i){
                sums[i] = (int)((((long)sums[i]) * mults[i]) % MOD);
                sums[i] = (sums[i] + sums[i-1]) % MOD;
            }
            System.out.print(sums[length]);
        } else {
            System.out.print(sums[1]);
        }
    }
    /*
    private static void print(int[] ar){
        StringBuffer sb = new StringBuffer();
        for(int v : ar){
            sb.append(v + " ");
        }
        System.out.println(sb);
    }
    */
}

Scor obtinut: 1.0

Submission ID: 464612850

Link challenge: https://www.hackerrank.com/challenges/p-sequences/problem

P-sequences