O(n ^ 2): Rabin-Karp vs. Trie
It\'s tempting to apply a sliding window technique here, however, it won\'t help us identify distinct subarrays.\n\nBecause constraints are low (n <= 200), we c
It\'s tempting to apply a sliding window technique here, however, it won\'t help us identify **distinct** subarrays.\n\nBecause constraints are low (n <= 200), we can just identify all valid subarrays *O(n ^ 2)*, and use a set to dedup them *O(n)*. So, the overall complexity would be *O(n ^ 3)*.\n\nFor O(n ^ 2) solution, we can use a rolling hash (Rabin-Karp). Note that we only need to check hashes for arrays of the same size, which reduces the collision probability.\n\nWe can also use a Trie to achieve a quadratic complexity - check the second solution below.\n\n#### Rolling Hash (Simple)\nWe need to do the collision check, but here I omitted it for simplicity (see third solution below if you want to handle collisions).\n**C++**\n```cpp\nint countDistinct(vector<int>& nums, int k, int p) {\n    int cnt[201] = {}, hash[201] = {}, res = 0;\n    for (int sz = 0; sz < nums.size(); ++sz) {\n        unordered_set<int> s;\n        for (int i = 0; i + sz < nums.size(); ++i) {\n            cnt[i] += nums[i + sz] % p == 0;\n            if (cnt[i] <= k) {\n                hash[i] = ((long long)hash[i] * 200 + nums[i + sz]) % 1000000007;\n                res += s.insert(hash[i]).second;\n            }\n        }\n    }\n    return res;\n}\n```\n#### Trie\nWe increment counters for each Trie node to detect if a substring is a duplicate.\n\n**C++**\n```cpp\nstruct Trie {\n    unordered_map<int, Trie*> ch;\n    int cnt = 0;\n    int insert(vector<int>& nums, int i, int k, int p) {\n        if (i == nums.size() || k - (nums[i] % p == 0) < 0)\n            return 0;\n        if (ch[nums[i]] == nullptr)\n            ch[nums[i]] = new Trie();\n        return (++ch[nums[i]]->cnt == 1) + \n            ch[nums[i]]->insert(nums, i + 1, k - (nums[i] % p == 0), p);\n    }\n};\nint countDistinct(vector<int>& nums, int k, int p) {\n    int res = 0;\n    Trie t;\n    for (int i = 0; i < nums.size(); ++i)\n        res += t.insert(nums, i, k, p);\n    return res;\n}\n```\n#### Rolling Hash (Collision Check)\n**C++**\n```cpp\nint countDistinct(vector<int>& nums, int k, int p) {\n    int cnt[201] = {}, hash[201] = {}, res = 0;\n    for (int sz = 0; sz < nums.size(); ++sz) {\n        unordered_map<int, vector<int>> s;\n        auto collision = [&](const auto &ids, int i) {\n            for (int j : ids)\n                if (equal(begin(nums) + i, begin(nums) + i + sz + 1, begin(nums) + j))\n                    return true;\n            return false;\n        };\n        for (int i = 0; i + sz < nums.size(); ++i) {\n            cnt[i] += nums[i + sz] % p == 0;\n            if (cnt[i] <= k) {\n                hash[i] = ((long long)hash[i] * 200 + nums[i + sz]) % 1000000007;\n                if (!collision(s[hash[i]], i)) {\n                    s[hash[i]].push_back(i);\n                    ++res;\n                }\n            }\n        }\n    }\n    return res;\n}\n```
['C']