Нахождение общего числа подмассивов в K каскадных массивах с суммой <= M

Question

При заданном массиве и K (сколько раз он сцеплен. Нам нужно найти общее количество смежных подмассивов с суммой <= заданное значение M </p>

I вычислили все возможные подмассивы для каждого индекса в исходном массиве, проверив, насколько далеко я могу go до того, как моя сумма превысит М. При вычислении этого я могу достичь конца, прежде чем моя сумма превысит М, иначе все еще существуют (K-массивы used) массивы left Подмножества, которые я вычислил для одного массива, я умножу на (K-used) для оставшихся нескольких индексов с правой стороны. Я снова буду опираться на условие, упомянутое в методе findTotalSubsets. Приведенное ниже решение работает для небольших входы, но в целом это не решение для коррекции в зависимости от платформы.

public class ModifiedSubarraySumProblem {
    static int MOD = 1000000007;

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        byte t = scan.nextByte();
        while (t-- > 0) {
            int[] arr = new int[scan.nextInt()], subsetsStartingWithCount = new int[arr.length];
            long K = scan.nextLong();
            int M = scan.nextInt();

            for (int i = 0; i < arr.length; i++)
                arr[i] = scan.nextInt();

            long subsetCount = findSubsets(arr, subsetsStartingWithCount, K, M);
            if (subsetCount == 0 || K == 1)
                System.out.println(subsetCount % MOD);
            else
                System.out.println(findTotalSubsets(arr, subsetsStartingWithCount, subsetCount, K, M));
        }
    }

    private static int findTotalSubsets(int[] arr, int[] subsetsStartingWithCount, long subsetCount, long K, int M) {
        int n = arr.length;
        long span, left;
        if (arr[0] >= M || arr[n - 1] >= M || n > 1 && arr[0] + arr[n - 1] > M)
            return (int) ((K % MOD) * (subsetCount % MOD) % MOD);
        span = (int) Math.ceil((subsetsStartingWithCount[n - 1] - 1) / (double) n);
        if (K - span > 0)
            subsetCount = (K - span) * subsetCount;
        left = span * n;
        for (int i = 0; i < n; i++) {
            if (subsetsStartingWithCount[i] > (left - i))
                subsetCount = subsetCount + (left - i);
            else
                subsetCount = subsetCount + subsetsStartingWithCount[i];
        }
        span = (span - 1) * n;
        subsetCount = subsetCount + span * (span + 1) / 2;
        return (int) (subsetCount % MOD);
    }

    private static long findSubsets(int[] input, int[] output, long K, int M) {
        long subsetCount = 0, j = 0;
        int sum = 0, n = input.length;
        for (int i = 0; i < n; i++) {
            if (i != 0) {
                sum = sum - input[i - 1];
            }
            // n*k might overflow, subarray can never go beyond 1000000
            if ((n * K) / n != K)
                K = 10000000000l;
            else
                K = n * K;
            for (; j < K; j++) {
                if (sum + input[(int) (j % n)] <= M)
                    sum += input[(int) (j % n)];
                else
                    break;
            }
            output[i] = (int) j - i;
            subsetCount += output[i];
        }
        return subsetCount;
    }

}