3757. Number of Effective Subsequences Hard

1/**
2 * [3757] Number of Effective Subsequences
3 *
4 * You are given an integer array nums.
5 * The strength of the array is defined as the bitwise OR of all its elements.
6 * A <span data-keyword="subsequence-array-nonempty">subsequence</span> is considered effective if removing that subsequence strictly decreases the strength of the remaining elements.
7 * Return the number of effective subsequences in nums. Since the answer may be large, return it modulo 10^9 + 7.
8 * The bitwise OR of an empty array is 0.
9 *  
10 * <strong class="example">Example 1:
11 * <div class="example-block">
12 * Input: <span class="example-io">nums = [1,2,3]</span>
13 * Output: <span class="example-io">3</span>
14 * Explanation:
15 * 
16 * 	The Bitwise OR of the array is 1 OR 2 OR 3 = 3.
17 * 	Subsequences that are effective are:
18 * 	
19 * 		[1, 3]: The remaining element [2] has a Bitwise OR of 2.
20 * 		[2, 3]: The remaining element [1] has a Bitwise OR of 1.
21 * 		[1, 2, 3]: The remaining elements [] have a Bitwise OR of 0.
22 * 	
23 * 	
24 * 	Thus, the total number of effective subsequences is 3.
25 * </div>
26 * <strong class="example">Example 2:
27 * <div class="example-block">
28 * Input: <span class="example-io">nums = [7,4,6]</span>
29 * Output: <span class="example-io">4</span>
30 * Explanation:​​​​​​​
31 * 
32 * 	The Bitwise OR of the array is 7 OR 4 OR 6 = 7.
33 * 	Subsequences that are effective are:
34 * 	
35 * 		[7]: The remaining elements [4, 6] have a Bitwise OR of 6.
36 * 		[7, 4]: The remaining element [6] has a Bitwise OR of 6.
37 * 		[7, 6]: The remaining element [4] has a Bitwise OR of 4.
38 * 		[7, 4, 6]: The remaining elements [] have a Bitwise OR of 0.
39 * 	
40 * 	
41 * 	Thus, the total number of effective subsequences is 4.
42 * </div>
43 * <strong class="example">Example 3:
44 * <div class="example-block">
45 * Input: <span class="example-io">nums = [8,8]</span>
46 * Output: <span class="example-io">1</span>
47 * Explanation:
48 * 
49 * 	The Bitwise OR of the array is 8 OR 8 = 8.
50 * 	Only the subsequence [8, 8] is effective since removing it leaves [] which has a Bitwise OR of 0.
51 * 	Thus, the total number of effective subsequences is 1.
52 * </div>
53 * <strong class="example">Example 4:
54 * <div class="example-block">
55 * Input: <span class="example-io">nums = [2,2,1]</span>
56 * Output: <span class="example-io">5</span>
57 * Explanation:
58 * 
59 * 	The Bitwise OR of the array is 2 OR 2 OR 1 = 3.
60 * 	Subsequences that are effective are:
61 * 	
62 * 		[1]: The remaining elements [2, 2] have a Bitwise OR of 2.
63 * 		[2, 1] (using nums[0], nums[2]): The remaining element [2] has a Bitwise OR of 2.
64 * 		[2, 1] (using nums[1], nums[2]): The remaining element [2] has a Bitwise OR of 2.
65 * 		[2, 2]: The remaining element [1] has a Bitwise OR of 1.
66 * 		[2, 2, 1]: The remaining elements [] have a Bitwise OR of 0.
67 * 	
68 * 	
69 * 	Thus, the total number of effective subsequences is 5.
70 * </div>
71 *  
72 * Constraints:
73 * 
74 * 	1 <= nums.length <= 10^5
75 * 	1 <= nums[i] <= 10^6
76 * 
77 */
78pub struct Solution {}
79
80// problem: https://leetcode.com/problems/number-of-effective-subsequences/
81// discuss: https://leetcode.com/problems/number-of-effective-subsequences/discuss/?currentPage=1&orderBy=most_votes&query=
82
83// submission codes start here
84
85impl Solution {
86    pub fn count_effective(nums: Vec<i32>) -> i32 {
87        0
88    }
89}
90
91// submission codes end
92
93#[cfg(test)]
94mod tests {
95    use super::*;
96
97    #[test]
98    fn test_3757() {
99    }
100}
101