生成函数求递推通项的入门题。
不妨假设 \(\alpha = 233\)，\(\beta = 666\)。
可以快速得到 \(a_i\) 的 OGF：
\[G(x) = \frac{x}{1-\alpha x - \beta x^2} \]OGF 的核心式子是 \((a+b)^n\)，我们考虑把分式下面化成二项式：
\[1-\alpha x - \beta x^2 = (1-Ax)(1-Bx) \Rightarrow \begin{cases}A = \frac{\alpha + k}{2} \\ B = \frac{\alpha - k}{2} \\ k = \sqrt{\alpha^2-4\beta}\end{cases} \]然后发现上式可转化为：
\[G(X) = L(\frac{1}{1-Ax} - \frac{1}{1-Bx}),L = \frac{1}{k} \]所以：\([x^n]G(x) = L(A^n - B^n)\)
现在还有两个问题。
- 快速幂 \(O(\log{n})\)，总时间复杂度 \(O(T\log{n})\)，会时超。
使用光速幂 \(O(1)\) 解决。
具体来说，例如我们要求 \(A^{x}\)。
首先费马小定理，可以让 \(x \in [0,10^9+5]\)。
然后我们可以预处理 \(A^{10000x}\)，\(x \in [0,100001]\)。
再处理 \(A^{x}\)，\(x \in [0,10000]\)。
最后 \(x = 10000a + b\)，用预处理的值 \(O(1)\) 计算。
- 求 \(k\)（二次根式的逆元）
\(k = \sqrt{56953}\)，只需要暴力找到 \(k^2 = 56953\)。求得 \(k = 188305837\)。
#include <bits/stdc++.h>
#define int unsigned long long
const int mod = 1e9 + 7;
using namespace std;
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;
}
}
int T;
int fpow(int a, int b)
{
int r = 1;
while (b)
{
if (b & 1)
r = r * a % mod;
a = a * a % mod;
b >>= 1;
}
return r % mod;
}
int ans;
int ab[100005], bb[100005], ar[10005], br[10005];
int apow(int b)
{
return ab[b / 10000] * ar[b % 10000] % mod;
}
int bpow(int b)
{
return bb[b / 10000] * br[b % 10000] % mod;
}
signed main()
{
scanf("%llu", &T);
Mker::init();
int inv = fpow(2, mod - 2);
int sqrdelta = 188305837;
int A = (233 + sqrdelta) % mod * inv % mod;
int B = (233 - sqrdelta + mod) % mod * inv % mod;
int k = fpow(sqrdelta, mod - 2);
ar[0] = ab[0] = bb[0] = br[0] = 1;
for (int i = 1; i < 10000; i++)
{
ar[i] = ar[i - 1] * A % mod;
br[i] = br[i - 1] * B % mod;
}
ab[1] = ar[9999] * A % mod;
bb[1] = br[9999] * B % mod;
for (int i = 2; i <= 100001; i++)
{
ab[i] = ab[i - 1] * ab[1] % mod;
bb[i] = bb[i - 1] * bb[1] % mod;
}
while (T--)
{
int n = Mker::rand();
n %= mod-1;
if (n <= 1)
{
ans ^= n;
}
else
{
ans ^= (apow(n) - bpow(n) + mod) % mod * k % mod;
}
}
cout << ans;
return 0;
}