洛谷5110 块速递推

$$ \text{特征根}x_1=\frac{233}{2}+\frac{13\sqrt{337}}{2},x_2=-\frac{13\sqrt{337}}{2}+\frac{233}{2} \\ \text{通项}a_n=ax_{1}^{n}+bx_{2}^{n} \\ \text{联立方程}\begin{cases} 0=a+b\\ 1=x_1a+x_2b\\ \end{cases} \\ \text{解出}a=\frac{\sqrt{337}}{4381},b=-\frac{\sqrt{337}}{4381} \\ \text{根据欧拉准则，}\left( 337 \right) ^{\frac{p-1}{2}}=\text{1,故求解二次剩余}216284168^2\equiv 337\left( mod\,\,10^9+7 \right) \\ \text{故在模}10^9+\text{7意义下，}x_1=\text{905847205,}x_2=94153035 \\ a=766769301 \\ \text{故}a_n=766769301\left( 905847205^n-94153035^n \right) \\ \text{对于一次询问，令}x=km+p\left( m\text{为块大小} \right) \text{，则有}x_{1}^{km+p}=x_{1}^{km}\times x_{1}^{p},\text{其中}p<m \\ \text{按照大小为}m\text{分块即可。} \\ \\ $$

#include <cstdio>
#include <iostream>
using int_t = long long int;
using std::cin;
using std::cout;
using std::endl;

namespace Mker {
unsigned long long SA, SB, SC;
void init() { scanf("%llu%llu%llu", &SA, &SB, &SC); }
unsigned long long rand() {
    SA ^= SA << 32, SA ^= SA >> 13, SA ^= SA << 1;
    unsigned long long t = SA;
    SA = SB, SB = SC, SC ^= t ^ SA;
    return SC;
}
}  // namespace Mker
const int_t mod = 1e9 + 7;
const int_t phi = mod - 1;
const int_t a = 766769301;
const int_t x1 = 905847205;
const int_t x2 = 94153035;
const int_t BLOCK_SIZE = 65536;
int T;
int_t x1s[mod / BLOCK_SIZE + 1], x2s[mod / BLOCK_SIZE + 1];
int_t x1b[BLOCK_SIZE], x2b[BLOCK_SIZE];
int_t power(int_t base, int_t index) {
    int_t result = 1;
    while (index) {
        if (index & 1) result = result * base % mod;
        index >>= 1;
        base = base * base % mod;
    }
    return result;
}
int main() {
    cin >> T;

    x1s[0] = x2s[0] = 1;
    int_t prex1 = power(x1, BLOCK_SIZE);
    int_t prex2 = power(x2, BLOCK_SIZE);
    for (int_t i = 1; i <= mod / BLOCK_SIZE; i++) {
        x1s[i] = x1s[i - 1] * prex1 % mod;
        x2s[i] = x2s[i - 1] * prex2 % mod;
    }
    x1b[0] = x2b[0] = 1;
    for (int_t i = 1; i < BLOCK_SIZE; i++) {
        x1b[i] = x1b[i - 1] * x1 % mod;
        x2b[i] = x2b[i - 1] * x2 % mod;
    }
    int_t result = 0;
    Mker::init();
    while (T--) {
        // int_t curr = 0;
        int x = (unsigned long long int)Mker::rand() % phi;
        int_t curr = ((x1s[x >> 16] * x1b[x & ((1 << 16) - 1)] -
                       x2s[x >> 16] * x2b[x & ((1 << 16) - 1)]) %
                          mod +
                      mod) %
                     mod * a % mod;
        result ^= curr;
    }
    cout << result << endl;
    return 0;
}