2019 南昌ICPC网络赛 H题 The Nth Item （二阶线性数列递推+光速幂） or （矩阵快速幂+广义斐波那契循环节）

传送门：https://nanti.jisuanke.com/t/41355

题意

$$F_0=0\;\;F_1 =1$$

$$F_{n}=3F_{n-1}+2F_{n-2}(n\ge 2)$$

$对每一个询问，输出F_n。$

思路

$如果是单矩阵快速幂的话，O(8*1e7*log(10^9))T飞了。$

二阶线性数列递推+快速幂优化

$我们知道，对于二阶线性数列递推，就是假设F_n=x^n，然后解出x^n=ax^{n-1}+bx^{x-2}.$

$如果有二实数根，则为F(n)=Ax_1^{n}+Bx_2^{n}$ $如果有一实数根，则为F(n)=(A+Bn)x^n$

$设F_n=x^n，则：$

$$x^n=3x^{n-1}+2x^{n-2}$$

$$x^2-3x-2=0$$

$$x1=\frac{3+\sqrt {17}}{2}\;\;\;\;x2=\frac{3-\sqrt{17}}{2}$$

$然后把F_0=0\;\;F_1 =1带入得：$

$$F_{n}=\frac{1}{\sqrt{17}}((\frac{3+\sqrt{17}}{2})^n+(\frac{3-\sqrt{17}}{2})^n)$$

$有\sqrt {17}怎么办？用二次剩余处理出来，程序跑出来应该是\sqrt{17}\%(998244353)=524399943.$ $注意:二次剩余处理出来的有两个值，取一个就行。$

$那么最后处理出来为$ $$F_n=559329360*(262199973^n-736044383^n)\;\;mod\;\;998244353$$

$到这里，仍然还不行，因为复杂度为O(1e7*log_2(1e18))也会T，而这里的log是快速幂的复杂度。$ $怎么办？光速幂！$

$因为我们快速幂是根据进制选择来确定复杂度的，比如log_2就是2进制，所以我们要扩大进制优化。$

$因为n有1e18，所以我按照2^{16}进制进行求幂，在用欧拉降幂优化后，只有两个权值1和65536。$

$以262199973^n为例，262199973^n=262199973^{n\%65536}+(262199973^2)^{(n\%65536^2)/65536}$ $736044383^n同理。$

$这样，复杂度从log_2n变为log_{65536}^n。$

$因为会有1e7次运算，所以中间可以加上记忆化剪枝。$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
##include "bits/stdc++.h"
using namespace std;

typedef long long ll;

const ll mod = 998244353;

ll A = 262199973;
ll B = 736044383;
ll invsqrt17 = 559329360;
vector<ll> x1(2),  x2(2);

ll quick\_pow(ll a, ll b) {
   ll ans = 1;
   while(b) {
       if(b & 1) ans = ans * a % mod;
       a = a * a % mod;
       b >>= 1;
   }
   return ans;
}

ll v\_pow1(ll a, ll b) {
    ll ans = 1;
    ll base = 65536, k = 1;
    for(int i = 0;i < 2; i++) {
        ans = ans * quick\_pow(x1[i], (b % (k * base)) / k) % mod;
        k = k * base;
    }
    return ans;
}

ll v\_pow2(ll a, ll b) {
    ll ans = 1;
    ll base = 65536, k = 1;
    for(int i = 0;i < 2; i++) {
        ans = ans * quick\_pow(x2[i], (b % (k * base)) / k) % mod;
        k = k * base;
    }
    return ans;
}
map<ll, ll> mp;

ll f(ll n) {
    if(mp[n]) return mp[n];
    ll ans = invsqrt17 * (v\_pow1(A, n) - v\_pow2(B, n)) % mod;
    return mp[n] = (ans % mod + mod) % mod;
}

void solve() {
    ll q, n; cin >> q >> n;
    x1[0] = A; x1[1] = quick\_pow(A, 65536);
    x2[0] = B; x2[1] = quick\_pow(B, 65536);
    ll ans = f(n % (mod - 1)), sum = f(n % (mod - 1));
    for(int i = 1;i < q; i++) {
        n ^= (sum * sum);
        sum = f(n % (mod - 1));
        ans ^= sum;
    }
    cout << ans << endl;
}

signed main() {
    solve();
}

矩阵快速幂+广义斐波那契循环节

$对于上面二次剩余的方法，由于会有局限性，比如\sqrt {13}就没有解，而对于循环节，这是通用性。$

$对于F_n=aF_{n-1}+bF_{n-2}，这是被称为广义斐波那契数列。$

$可以证明，F_n\;mod\;p是有循环节的。$

$设c=a^2+4b，如果c是模p的二次剩余时，枚举所有的p-1的因子，找到最小的因子x使得：$

$$ \begin{bmatrix} a& b\ 1& 0 \end{bmatrix}^x=\begin{bmatrix} 1 & 0\ 0 & 1 \end{bmatrix} $$

$则x为循环节。$

$如果c不是模p的二次剩余时，枚举所有的p^2-1的因子，找到最小的因子x，方法如上。$

$在这里，a^2+4b=17是模p的二次剩余，得出循环节为\frac{p-1}{2}=499122476。则F(N)=F(N\;\%\;499122476)$

Code

本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2021/03/26/2019-icpc-nanchang-online-h/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！