多项式与生成函数

快速沃尔什变换

快速沃尔什变换: https://oi-wiki.org/math/poly/fwt/

题目	难度
3514. 不同 XOR 三元组的数目 II	中等

3514. 不同 XOR 三元组的数目 II

public class Solution3514 {
    // 253ms
    static class V1 {
        public int uniqueXorTriplets(int[] nums) {
            // int U = 1 << bitsLen(1500);
            final int U = 2048;

            boolean[] has = new boolean[U];
            for (int i = 0; i < nums.length; i++) {
                for (int j = i; j < nums.length; j++) {
                    has[nums[i] ^ nums[j]] = true;
                }
            }

            boolean[] has3 = new boolean[U];
            for (int xy = 0; xy < U; xy++) {
                if (!has[xy]) {
                    continue;
                }
                for (int z : nums) {
                    has3[xy ^ z] = true;
                }
            }

            int ans = 0;
            for (boolean b : has3) {
                if (b) ans++;
            }
            return ans;
        }
    }

    // 50ms
    static class V2 {
        // 快速沃尔什变换 https://oi-wiki.org/math/poly/fwt/
        private void fwtXOR(long[] a, int rsh) {
            int n = a.length;
            for (int l = 2, k = 1; l <= n; l <<= 1, k <<= 1) {
                for (int i = 0; i < n; i += l) {
                    for (int j = 0; j < k; j++) {
                        long aij = a[i + j], aijk = a[i + j + k];
                        a[i + j] = (aij + aijk) >> rsh;
                        a[i + j + k] = (aij - aijk) >> rsh;
                    }
                }
            }
        }

        private long[] fwtXOR3(long[] a) {
            fwtXOR(a, 0);
            for (int i = 0; i < a.length; i++) {
                long x = a[i];
                a[i] *= x * x;
            }
            fwtXOR(a, 1);
            return a;
        }

        public int uniqueXorTriplets(int[] nums) {
            // int U = 1 << bitsLen(1500);
            final int U = 2048;
            long[] cnt = new long[U];
            for (int x : nums) {
                cnt[x]++;
            }
            int ans = 0;
            for (long c : fwtXOR3(cnt)) {
                if (c > 0) ans++;
            }
            return ans;
        }
    }
}

（全文完）