$$ \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; }