Added task 3757

javadev · web-flow · commit 6b74c45fb1e9 · 2026-04-25T13:48:48.000+03:00
diff --git a/src/main/java/g3701_3800/s3757_number_of_effective_subsequences/Solution.java b/src/main/java/g3701_3800/s3757_number_of_effective_subsequences/Solution.java
@@ -0,0 +1,65 @@
+package g3701_3800.s3757_number_of_effective_subsequences;
+
+// #Hard #Array #Dynamic_Programming #Math #Bit_Manipulation #Combinatorics #Weekly_Contest_477
+// #Senior_Staff #2026_04_25_Time_128_ms_(95.71%)_Space_85.91_MB_(18.57%)
+
+public class Solution {
+    private static final int MOD = 1_000_000_007;
+
+    public int countEffective(int[] nums) {
+        int n = nums.length;
+        int t = 0;
+        for (int v : nums) {
+            t |= v;
+        }
+        if (t == 0) {
+            return 0;
+        }
+        int[] bits = new int[20];
+        int m = 0;
+        for (int b = 0; b < 20; ++b) {
+            if (((t >> b) & 1) != 0) {
+                bits[m++] = b;
+            }
+        }
+        int s = 1 << m;
+        int[] freq = new int[s];
+        for (int v : nums) {
+            int m1 = 0;
+            for (int j = 0; j < m; ++j) {
+                if (((v >> bits[j]) & 1) != 0) {
+                    m1 |= 1 << j;
+                }
+            }
+            freq[m1]++;
+        }
+        int[] f = new int[s];
+        System.arraycopy(freq, 0, f, 0, s);
+        for (int i = 0; i < m; ++i) {
+            for (int mask = 0; mask < s; ++mask) {
+                if ((mask & (1 << i)) != 0) {
+                    f[mask] += f[mask ^ (1 << i)];
+                }
+            }
+        }
+        long[] p2 = new long[n + 1];
+        p2[0] = 1;
+        for (int i = 1; i <= n; ++i) {
+            p2[i] = (p2[i - 1] << 1) % MOD;
+        }
+        long ans = 0;
+        int all = s - 1;
+        for (int bmask = 1; bmask < s; ++bmask) {
+            int comp = all ^ bmask;
+            int cnt = f[comp];
+            long add = p2[cnt];
+            if (Integer.bitCount(bmask) % 2 == 1) {
+                ans = (ans + add) % MOD;
+            } else {
+                ans = (ans - add) % MOD;
+            }
+        }
+        ans = (ans % MOD + MOD) % MOD;
+        return (int) ans;
+    }
+}
diff --git a/src/main/java/g3701_3800/s3757_number_of_effective_subsequences/readme.md b/src/main/java/g3701_3800/s3757_number_of_effective_subsequences/readme.md
@@ -0,0 +1,78 @@
+3757\. Number of Effective Subsequences
+
+Hard
+
+You are given an integer array `nums`.
+
+The **strength** of the array is defined as the **bitwise OR** of all its elements.
+
+A **subsequence** is considered **effective** if removing that subsequence **strictly decreases** the strength of the remaining elements.
+
+Return the number of **effective subsequences** in `nums`. Since the answer may be large, return it **modulo** <code>10<sup>9</sup> + 7</code>.
+
+The bitwise OR of an empty array is 0.
+
+**Example 1:**
+
+**Input:** nums = [1,2,3]
+
+**Output:** 3
+
+**Explanation:**
+
+*   The Bitwise OR of the array is `1 OR 2 OR 3 = 3`.
+*   Subsequences that are effective are:
+    *   `[1, 3]`: The remaining element `[2]` has a Bitwise OR of 2.
+    *   `[2, 3]`: The remaining element `[1]` has a Bitwise OR of 1.
+    *   `[1, 2, 3]`: The remaining elements `[]` have a Bitwise OR of 0.
+*   Thus, the total number of effective subsequences is 3.
+
+**Example 2:**
+
+**Input:** nums = [7,4,6]
+
+**Output:** 4
+
+**Explanation:**
+
+*   The Bitwise OR of the array is `7 OR 4 OR 6 = 7`.
+*   Subsequences that are effective are:
+    *   `[7]`: The remaining elements `[4, 6]` have a Bitwise OR of 6.
+    *   `[7, 4]`: The remaining element `[6]` has a Bitwise OR of 6.
+    *   `[7, 6]`: The remaining element `[4]` has a Bitwise OR of 4.
+    *   `[7, 4, 6]`: The remaining elements `[]` have a Bitwise OR of 0.
+*   Thus, the total number of effective subsequences is 4.
+
+**Example 3:**
+
+**Input:** nums = [8,8]
+
+**Output:** 1
+
+**Explanation:**
+
+*   The Bitwise OR of the array is `8 OR 8 = 8`.
+*   Only the subsequence `[8, 8]` is effective since removing it leaves `[]` which has a Bitwise OR of 0.
+*   Thus, the total number of effective subsequences is 1.
+
+**Example 4:**
+
+**Input:** nums = [2,2,1]
+
+**Output:** 5
+
+**Explanation:**
+
+*   The Bitwise OR of the array is `2 OR 2 OR 1 = 3`.
+*   Subsequences that are effective are:
+    *   `[1]`: The remaining elements `[2, 2]` have a Bitwise OR of 2.
+    *   `[2, 1]` (using `nums[0]`, `nums[2]`): The remaining element `[2]` has a Bitwise OR of 2.
+    *   `[2, 1]` (using `nums[1]`, `nums[2]`): The remaining element `[2]` has a Bitwise OR of 2.
+    *   `[2, 2]`: The remaining element `[1]` has a Bitwise OR of 1.
+    *   `[2, 2, 1]`: The remaining elements `[]` have a Bitwise OR of 0.
+*   Thus, the total number of effective subsequences is 5.
+
+**Constraints:**
+
+*   <code>1 <= nums.length <= 10<sup>5</sup></code>
+*   <code>1 <= nums[i] <= 10<sup>6</sup></code>
diff --git a/src/test/java/g3701_3800/s3757_number_of_effective_subsequences/SolutionTest.java b/src/test/java/g3701_3800/s3757_number_of_effective_subsequences/SolutionTest.java
@@ -0,0 +1,28 @@
+package g3701_3800.s3757_number_of_effective_subsequences;
+
+import static org.hamcrest.CoreMatchers.equalTo;
+import static org.hamcrest.MatcherAssert.assertThat;
+
+import org.junit.jupiter.api.Test;
+
+class SolutionTest {
+    @Test
+    void countEffective() {
+        assertThat(new Solution().countEffective(new int[] {1, 2, 3}), equalTo(3));
+    }
+
+    @Test
+    void countEffective2() {
+        assertThat(new Solution().countEffective(new int[] {7, 4, 6}), equalTo(4));
+    }
+
+    @Test
+    void countEffective3() {
+        assertThat(new Solution().countEffective(new int[] {8, 8}), equalTo(1));
+    }
+
+    @Test
+    void countEffective4() {
+        assertThat(new Solution().countEffective(new int[] {2, 2, 1}), equalTo(5));
+    }
+}
