[Java | Strict O(n^2) | Using Hashing with Polynomial Function]
\n/*\n    NOTE: Concept Wise it can be tagged in Hard Category.\n    \n    Tool/Technique you need to add, into your toolbox\n    ------------------------------
```\n/*\n    NOTE: Concept Wise it can be tagged in Hard Category.\n    \n    Tool/Technique you need to add, into your toolbox\n    --------------------------------------------------\n        + Two subarays are equal or NOT can be checked in O(1) time.\n                - Provided pre-computation time complexity O(n * n), where n = len(given_array)\n                - Like: hashes[l1][r1] == hashes[l2][r2], where first subarray is : nums[l1:r1]\n                   and second subarray is : nums[l2:r2], indices are inclusive.\n        + Look at the beauty of Hashing. [alongwith Prime + Polynomial + Modulo Operator(loved it)]\n        \n    NOTE: The larger "M"(for mod) you\'ve, the more hashes will have.\n*/\n\nclass Solution {\n\t \n\t// <= 40th [173] prime number didn\'t work well for all test-cases. Ir-respective of what \n\t// M = 10^9 + 7 / 10^15 + 7 is.\n    private static final int P = 229; // 229 = 50th Prime Number, 541 = 100th prime number\n    private static final long M = (long)(1e15 + 7);\n    private static final long[] PP;\n    private static final int MAX_LENGTH = 2 * 1_00;\n\n    static {\n        PP = new long[MAX_LENGTH + 1];\n        PP[0] = P;\n        for(int i = 1; i <= MAX_LENGTH; i += 1) {\n            PP[i] = (PP[i - 1] % M * P % M) % M;\n        }\n    }\n\n    private void computeHashesForAllSubarrays(int[] nums, long[][] hashes, int n) {\n\t\t// hashes[i][j] = is the unique hash value for subarray nums[i:j]\n        for(int i = 0; i < n; i += 1) {\n            long subHash = 0;\n            for(int j = i; j < n; j += 1) {\n                int ele = nums[j];\n                subHash += (PP[j - i] * ele) % M;\n                hashes[i][j] = subHash;\n            }\n        }\n    }\n    \n    private void buildDivisibleCountForAllSubarrays(int[] nums, int[][] count, int n, int p) {\n        // count[i][j] = returns how many elements are there in the subarray\n        // nums[i:j], divisible by p. -> Helps to check (count_of_divisibles <= k) in O(1) time\n        for(int i = 0; i < n; i += 1) {\n            for(int j = i; j < n; j += 1) {\n                int rem = nums[j] % p;\n                count[i][j] = rem == 0 ? 1 : 0;\n                // Computing prefix count array\n                if(j > 0) {\n                    count[i][j] = rem == 0 ? count[i][j - 1] + 1 : count[i][j - 1];\n                }\n                // Actual computation where storing(at count[i][j]) how many elements\n                // are divisible by p in the sub-array (i, j)\n                count[i][j] = (count[i][j] - count[i][i]) + (nums[i] % p == 0 ? 1 : 0);\n            }\n        }\n    }\n    \n    public int countDistinct(int[] nums, int k, int p) {\n        int n = nums.length, countSubarrays = 0;\n        int[][] count = new int[n][n];\n        long[][] hashes = new long[n][n];\n        \n        buildDivisibleCountForAllSubarrays(nums, count, n, p);\n        computeHashesForAllSubarrays(nums, hashes, n);\n        \n        Set<Long> subarrayHash = new HashSet<>();\n        \n        for(int i = 0; i < n; i += 1) {\n            for(int j = i; j < n; j += 1) {\n                if(count[i][j] <= k) {\n                    if(!subarrayHash.contains(hashes[i][j])) {\n                        countSubarrays += 1;\n                        subarrayHash.add(hashes[i][j]);\n                    }\n                }\n            }\n        }\n        \n        return countSubarrays;\n    }\n}\n```
['Prefix Sum', 'Java']