C++ Trie Solution With Comments
\n// approach: \n// for all subarray starting from i (from 0 to n-1)\n// insert only the maximum valid subarray in the trie\n// if you make a new node in the tr
```\n// approach: \n// for all subarray starting from i (from 0 to n-1)\n// insert only the maximum valid subarray in the trie\n// if you make a new node in the trie, implies that this is a distinct subarray\n// keep a count (cnt) in the Trie, to count the number of distinct subarrays (the number of times you had to create a new node).\nclass TrieNode{\n    int cnt=0;\n    public:\n    unordered_map<int,TrieNode*> next;\n    void insert(vector<int>arr){\n        TrieNode* node= this;\n        int n=arr.size();\n        for(int i=0;i<n;i++){\n            if(!node->next.count(arr[i])){\n                node->next[arr[i]]= new TrieNode();\n                this->cnt++;\n            }\n            node=node->next[arr[i]];\n        }\n    }\n    int getCount(){\n        return this->cnt;\n    }\n};\nclass Solution {\npublic:\n    int countDistinct(vector<int>& nums, int k, int p) {\n        int n=nums.size(),ans=0;\n        vector<bool> isDiv(n,false);\n        for(int i=0;i<n;i++){\n            isDiv[i]=(nums[i]%p==0); // if divisible, it sets isDiv[i] to true\n        }\n        TrieNode* node= new TrieNode();\n        for(int i=0;i<n;i++){\n            int cnt=0; // to count the number of elements divisible by p, in the current subarray\n            vector<int>temp;\n            for(int j=i;j<n;j++){\n                cnt+= isDiv[j];\n                if(cnt>k)\n                    break;\n                temp.push_back(nums[j]);\n            }\n            node->insert(temp); \n        }\n        return node->getCount();\n    }\n};\n```
['Trie', 'C']