Subarrays Distinct Element Sum of Squares II
You are given a 0-indexed integer array nums.
The distinct count of a subarray of nums is defined as:
- Let
nums[i..j]be a subarray ofnumsconsisting of all the indices fromitojsuch that0 <= i <= j < nums.length. Then the number of distinct values innums[i..j]is called the distinct count ofnums[i..j].
Return the sum of the squares of distinct counts of all subarrays of nums.
Since the answer may be very large, return it modulo 10^9 + 7.
A subarray is a contiguous non-empty sequence of elements within an array.
Example 1
Input
nums = [1,2,1]Output
15The sum of the squares of the distinct counts in all subarrays is equal to 1^2 + 1^2 + 1^2 + 2^2 + 2^2 + 2^2 = 15.
Example 2
Input
nums = [2,2]Output
3The sum of the squares of the distinct counts in all subarrays is equal to 1^2 + 1^2 + 1^2 = 3.
Constraints
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^5