16109

问题陈述

时间限制为 4 秒。

如果一个序列的乘积可以表示为两个平方数之和，则该序列被称为好序列。例如：

{1, 1, 1} 是好序列，因为 $1\ast 1\ast 1=1=0^2+1^2$。
{6, 164, 15} 是好序列，因为 $6\ast 164\ast 15=14760={42}^2+{114}^2$。
{2, 3} 不是好序列，因为 $2\ast 3=6$，而 6 不可能表示为两个平方数的和。

一个序列 X 的子序列是指从 X 中删除零个或多个元素而保持剩余元素顺序不变得到的任何序列。如果两个相同序列的子序列通过删除不同的索引对应到不同序列上，则它们是不同的。

给定大小为 N 的数组 A，A 中的元素是正整数。

还给出了一些查询 Q。对于第 i 个查询，考虑由 A 中下标从 $QL[i]$ 到 $QR[i]$的元素形成的序列 $A_i$。第 $i$ 个查询的答案是序列 $A_i$ 的非空好子序列的数量。

计算所有查询的答案，并返回它们对 $998244353$ 取模的和。

为了保持输入尺寸较小，你只给出了 A，QL 和 QR 的前缀，在 $int[]$ 中使用以下伪代码生成完整的数组：

state = seed

A = Aprefix
while length(A) < N:
    state = (state * 1103515245 + 12345) modulo 2^31
    A.append( 1 + state modulo 10000000)

QL = QLprefix
QR = QRprefix
while len(L) < Q:
    state = (state * 1103515245 + 12345) modulo 2^31
    x = state modulo N
    state = (state * 1103515245 + 12345) modulo 2^31
    y = state modulo N
    QL.append( min(x,y) )
    QR.append( max(x,y) )
 

定义

• 类：TaleOfTwoSquares
• 方法：count
• 参数：int, int[]，int, int[]，int[]，int
• 返回值：int
• 方法签名：int count (int N, int[] Aprefix, int Q, int[] QLprefix, int[] QRprefix, int seed)

约束条件

• N 将在 $1$ 到 ${10}^5$ 之间，包括边界。
• Aprefix 将有 $0$ 到 $min(100,N)$个元素。
• Aprefix 的每个元素将在 $1$ 到 ${10}^7$ 之间，包括边界。
• Q 将在 $1$ 到 ${10}^5$ 之间，包括边界。
• QLprefix 将有 0 到 $min(100,Q)$个元素。
• QRprefix 将与 QLprefix 具有相同数量的元素。
• 对于每个 i，$0\le QLprefix[i]\le QRprefix[i]\le N-1$。
• seed 将在 $0$ 到 $2^{31}-1$ 之间，包括边界。

示例

0 .

8
{1, 1, 1, 6, 164, 15, 2, 3}
3
{0, 3, 6}
{2, 5, 7}
0

Returns: 11

在这个例子中，我们得到了整个数组 A、QL 和 QR。一共有三个查询。

• 第 0 个查询询问序列{1, 1, 1}。这个序列的 7 个非空子序列都是好序列。
• 第 1 个查询询问序列{6, 164, 15}。只有子序列{6, 15}，{164}和{6, 164, 15}是好序列。
• 第 2 个查询询问序列{2, 3}。只有子序列{2}是好序列。
  所有查询的答案之和为 $7+3+1=11$。

1 .

40
{2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2}
300
{}
{}
47

Returns: 800453880

每个序列的所有非空子序列都是好序列。

2 .

14
{47, 12345}
5
{4, 5}
{6, 7}
47

Returns: 11

你应该有以下数组：

A = {47, 12345, 5621309, 3614406, 1878299, 854092, 6820649, 3962434, 1250151, 3983528, 7736277, 8477438, 9514867, 2640324}
QL = {4, 5, 5, 1, 3}
QR = {6, 7, 8, 6, 6}

题解

一个数字可以被表示为两个平方数的和，当且仅当它所有形式为 $4K+3$ 的质因数出现偶数次。所以，当我们计算几个数字的乘积时，我们只关心它的质因数分解；因此，我们可以为每个 $A_i$ 存储一个位向量，表示这些质因数的奇数/偶数出现。

从现在开始，每当我谈到质数时，假定它们为形式为 $4K+3$（对于某个 $k\in Z$），并且读者熟悉向量空间的基础和高斯消元。如果您对在竞赛编程中如何应用这些概念不熟悉，请阅读这篇文章：使用线性代数技术解决异或相关问题的入门博客

现在，$A_i\le {10}^7$，因此质数的数量大约为 $3\ast {10}^5$。普通的高斯消元甚至使用位集合也可能很容易超时。不过，让我们假设从最高位到最低位进行高斯消元并在必要时进行异或操作。注意，当您遍历时，如果存在任何大于 $\sqrt{A_i}$ 的质因数（最多可以存在一个），一旦异或了它，就不会再有大于 $\sqrt{A_i}$ 的位了（因为之前只有一个位是打开的，现在您已经异或了它）。现在，您可以简单地模拟对低阶质数（即质数 $\le \sqrt{A_i}$）进行高斯消元，并单独处理那个最高位（如果存在的话）。这样，结合对低阶质数的位集合处理，就可以解决问题。

对于查询，让我们离线处理它们。让 $queries[l]$ 存储所有左端点为 $l$ 的查询。我们将从右侧将 $A_i$ 插入到我们的基向量中，其中 $i$ 从 $N-1$ 到 $0$。在我们插入索引 $i$ 处的元素之后，我们将回答所有在那里开始的查询，即 $queries[i]$ 中的查询。

我们将使用一个关于向量的线性组合的简单事实，但以聪明的方式来回答这些查询。假设我们将要尝试插入 $v$ 到我们的 $Basis$（如果结果是依赖的话，可能不会插入）。如果 $v=b_1+b_2+\cdots +b_k$（其中 $b_i\in Basis$），那么我们可以删除 $b_i$ 中的一个，并将 $v$ 放在它的位置，保持基向量不变。因此，我们在插入时将使用这一事实。我们将尝试保留基向量中左端的索引，以回答尽可能多的查询。我们可以贪婪地实现这一点：在插入 $v$ 时，每当我们要与一些 $b_i$ 进行异或操作时，我们将首先检查哪个索引最小，如果 $v$ 的索引小于 $b_i$，我们将 $swap(b_i,v)$。如果最终进行了交换，那么 $v$ 将成为基向量的一部分（代替 $b_i$），并且我们将使用 $b_i$ 进行高斯消元。否则，我们将像正常情况一样继续进行。更多细节，请参考附加的代码。

现在，当我们回答左端点为 $i$ 的查询时，我们将拥有基向量 $A[i:N]$，其具有可能的最小索引。因此，对于一个查询 $i$ 到 $R$，我们只需要计算基向量中索引 $\le R$ 的数量。这可以很容易地使用一些 BIT 或 set 完成。

让 $K$ 表示 $\le \sqrt{A_i}$ 的质数的数量（$=225$）。我们为每个质数存储一个大小为 $K$ 的 ../../算法知识/bitset 。在进行高斯消元时，我们手动处理大位数，然后按照常规程序处理低阶质数；因此，插入 $A_i$ 花费 $O(\frac{K^2}{64})$ 的时间。之后，在 $O(log(N))$ 的时间内回答 $O(log(N))$ 中的查询。因此，总体复杂度是 $O(N\cdot \frac{k^2}{64}+Q\cdot log(N))$，由使用 ../../算法知识/bitset 的高斯消元支配。

Reference sol in C++

代码

#include <bits/stdc++.h>
using namespace std;

const int SQRTMAX = 3162;
const int SMALL_PRIME_COUNT = 225;
const int SMALL_PRIMES[] = {3, 7, 11, 19, 23, 31, 43, 47, 59, 67, 71, 79, 83, 103, 107, 127, 131, 139, 151, 163, 167, 179, 191, 199, 211, 223, 227, 239, 251, 263, 271, 283, 307, 311, 331, 347, 359, 367, 379, 383, 419, 431, 439, 443, 463, 467, 479, 487, 491, 499, 503, 523, 547, 563, 571, 587, 599, 607, 619, 631, 643, 647, 659, 683, 691, 719, 727, 739, 743, 751, 787, 811, 823, 827, 839, 859, 863, 883, 887, 907, 911, 919, 947, 967, 971, 983, 991, 1019, 1031, 1039, 1051, 1063, 1087, 1091, 1103, 1123, 1151, 1163, 1171, 1187, 1223, 1231, 1259, 1279, 1283, 1291, 1303, 1307, 1319, 1327, 1367, 1399, 1423, 1427, 1439, 1447, 1451, 1459, 1471, 1483, 1487, 1499, 1511, 1523, 1531, 1543, 1559, 1567, 1571, 1579, 1583, 1607, 1619, 1627, 1663, 1667, 1699, 1723, 1747, 1759, 1783, 1787, 1811, 1823, 1831, 1847, 1867, 1871, 1879, 1907, 1931, 1951, 1979, 1987, 1999, 2003, 2011, 2027, 2039, 2063, 2083, 2087, 2099, 2111, 2131, 2143, 2179, 2203, 2207, 2239, 2243, 2251, 2267, 2287, 2311, 2339, 2347, 2351, 2371, 2383, 2399, 2411, 2423, 2447, 2459, 2467, 2503, 2531, 2539, 2543, 2551, 2579, 2591, 2647, 2659, 2663, 2671, 2683, 2687, 2699, 2707, 2711, 2719, 2731, 2767, 2791, 2803, 2819, 2843, 2851, 2879, 2887, 2903, 2927, 2939, 2963, 2971, 2999, 3011, 3019, 3023, 3067, 3079, 3083, 3119 };
vector<int> SMALL_PRIME_ID, pow2;

struct Fenwick1D { // {{{
    int size;
    vector<int> T;

    Fenwick1D(int maxval) {
        size = 1;
        while (size < maxval) size <<= 1;
        T.clear();
        T.resize(size+1,0);
    }

    void update(int x, int delta) { // assumes 1 <= x <= init_maxval
        while (x <= size) { T[x] += delta; x += x & -x; }
    }

    int sum(int x1, int x2) { // sum in the closed interval [x1,x2]
        int res=0;
        --x1;
        while (x2) { res += T[x2]; x2 -= x2 & -x2; }
        while (x1) { res -= T[x1]; x1 -= x1 & -x1; }
        return res;
    }

    int find(int sum) { // largest z such that sum( [1,z] ) <= sum
        int idx = 0, bitMask = size;
        while (bitMask && (idx < size)) {
            int tIdx = idx + bitMask;
            if (sum >= T[tIdx]) { idx=tIdx; sum -= T[tIdx]; }
            bitMask >>= 1;
        }
        return idx;
    }
}; // }}}

void init() {
    SMALL_PRIME_ID.clear();
    SMALL_PRIME_ID.resize(SQRTMAX+1, -1);
    for (int i=0; i<SMALL_PRIME_COUNT; ++i) SMALL_PRIME_ID[ SMALL_PRIMES[i] ] = i;
    pow2.clear();
    pow2.push_back(1);
    for (int i=1; i<100005; ++i) pow2.push_back( (pow2.back()*2) % 998244353 );
}

struct signature {
    bitset< SMALL_PRIME_COUNT > small_bits;
    int large_bit;
    signature() : large_bit(-1) {}

    int highest_prime() {
        if (large_bit != -1) return large_bit;
        for (int i=SMALL_PRIME_COUNT-1; i>=0; --i) if (small_bits.test(i)) return SMALL_PRIMES[i];
        return 0;
    }

    void do_xor(const signature &other) {
        if (other.large_bit != -1) {
            if (large_bit != -1) {
                assert( large_bit == other.large_bit );
                large_bit = -1;
            } else {
                large_bit = other.large_bit;
            }
        }
        small_bits ^= other.small_bits;
    }
};

ostream& operator<< (ostream& out, const signature &S) {
    /*
    int max = SMALL_PRIME_COUNT - 1;
    while (max > 0 && !S.small_bits.test(max)) --max;
    for (int i=0; i<=max; ++i) out << int( S.small_bits.test(i) );
    */
    if (S.large_bit != -1) out << S.large_bit << "+";
    for (int i=9; i>=0; --i) out << int(S.small_bits.test(i));
    return out;
}

struct query {
    int l, r;
};

bool operator< (const query &A, const query &B) {
    if (A.l != B.l) return A.l > B.l;
    return A.r < B.r;
}

signature get_signature(int N) {
    signature answer;
    for (int d=2; d*d<=N; ++d) {
        if (N % d) continue;
        int cnt = 0;
        while (N % d == 0) { ++cnt; N /= d; }
        if (d % 4 != 3) continue;
        if (cnt % 2 == 0) continue;
        answer.small_bits.set( SMALL_PRIME_ID[d] );
    }
    if (N > 1 && N % 4 == 3) {
        if (N > SQRTMAX) answer.large_bit = N; else answer.small_bits.set( SMALL_PRIME_ID[N] );
    }
    return answer;
}

struct TaleOfTwoSquares {
    int count(int N, vector<int> Aprefix, int Q, vector<int> Lprefix, vector<int> Rprefix, int seed) {
        init();

        long long state = seed;

        vector<int> A = Aprefix;
        while (int(A.size()) < N) {
            state = (state * 1103515245 + 12345) % (1LL << 31);
            A.push_back(1 + (state % 10000000));
        }

        if (N <= 20) for (int n=0; n<N; ++n) cout << A[n] << ", "; cout << endl;

        vector<int> L = Lprefix, R = Rprefix;
        while (int(L.size()) < Q) {
            state = (state * 1103515245 + 12345) % (1LL << 31);
            int x = state % N;
            state = (state * 1103515245 + 12345) % (1LL << 31);
            int y = state % N;
            L.push_back( min(x,y) );
            R.push_back( max(x,y) );
        }

        if (Q <= 20) for (int n=0; n<Q; ++n) cout << L[n] << ", "; cout << endl;
        if (Q <= 20) for (int n=0; n<Q; ++n) cout << R[n] << ", "; cout << endl;

        vector<signature> B;
        for (int n=0; n<N; ++n) B.push_back( get_signature(A[n]) );

        vector< vector<int> > query_by_L(N);
        for (int q=0; q<Q; ++q) query_by_L[ L[q] ].push_back( R[q] );

        Fenwick1D InBase(N+2);
        int answer = 0;
        unordered_map<int,int> base_by_highest_prime;

        for (int n=N-1; n>=0; --n) {
            // two dummy updates
            InBase.update(N+1,+1);
            InBase.update(N+1,-1);
            // add number A[n] to the base
            if (B[n].highest_prime() != 0) {
                InBase.update(n+1,+1);
                int where = n;
                while (true) {
                    int p = B[where].highest_prime();
                    if (p == 0) {
                        InBase.update(where+1,-1);
                        break;
                    }
                    if (!base_by_highest_prime.count(p)) {
                        base_by_highest_prime[p] = where;
                        break;
                    }
                    int nxt = base_by_highest_prime[p];
                    if (nxt > where) {
                        base_by_highest_prime[p] = where;
                        B[nxt].do_xor( B[where] );
                        where = nxt;
                    } else {
                        B[where].do_xor( B[nxt] );
                    }
                }
            }
            // answer queries that begin here
            for (int r : query_by_L[n]) {
                int length = r-n+1;
                int base_size = InBase.sum(n+1,r+1);
                answer += pow2[length-base_size] - 1;
                answer %= 998244353;
            }
        }

        return answer;
    }
};