2019南昌网络赛H The Nth Item（二阶线性数列递推 + 广义斐波那契循环节 + 分段打表）题解

题意：

传送门
已知(F(n)=3F(n-1)+2F(n-2) mod 998244353,F(0)=0,F(1)=1)，给出初始的(n_1)和询问次数(q)，设每一次的答案(a_i=F(n_i))，而(n_{i+1}=n_ioplus(a_i*a_i))，求(a_1oplus a_2dotsoplus a_q)。

思路：

原式是一个二次常数递归式，我们可以求得它的通项为：

[F(n)=frac{1}{sqrt{17}}[(frac{3+sqrt{17}}{2})^n-(frac{3-sqrt{17}}{2})^n] ]

经过二次剩余等乱七八糟的操作，我们能直接(O(qlogn))得到答案，但是时间还是太多。

1：

然后有一个广义斐波那契数列的循环节，那么用(unordered\_map)记忆化一下。

2：

因为直接(logn)求一个(F(n))会超时，那么使用分段打表把复杂度降到(O(1))。由扩展欧拉定理可得，(a^nequiv a^{n\%varphi(p)+varphi(p)} mod p)，那么公式中的指数上限降到(2(mod -1))。然后我们打表出(sqrt{2(mod -1)}<5e4)次幂的结果，那么只要小于(5e4)的幂次直接可得。然后打表打出(0*5e4,1*5e4dots5e4*5e4)次幂的结果，那么对于大于(5e4)的幂次可以转化为(a^{k*5e4}*a^c)前后结论都已打表，那么也是(O(1))即可求解。

代码：

//1
#include<map>
#include<set>
#include<queue>
#include<cmath>
#include<stack>
#include<ctime>
#include<vector>
#include<cstdio>
#include<string>
#include<cstring>
#include<sstream>
#include<iostream>
#include<algorithm>
#include<unordered_map>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int maxn = 1e6 + 5;
const int MAXM = 3e6;
const ll MOD = 998244353;
const ull seed = 131;
const int INF = 0x3f3f3f3f;

const ll r1 = 262199973, r2 = 736044383, invs17 = 559329360;
unordered_map<ll, ll> st;
ll ppow(ll a, ll b){
    ll ret = 1;
    while(b){
        if(b & 1) ret = ret * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return ret;
}
ll solve(ll n){
    if(st.count(n)) return st[n];
    return st[n] = (ppow(r1, n) - ppow(r2, n) + MOD) % MOD * invs17 % MOD;
}

int main(){
    st.clear();
    int q;
    ll n;
    scanf("%d%lld", &q, &n);
    ll ans = 0, tmp;
    for(int i = 1; i <= q; i++){
        tmp = solve(n);
        ans ^= tmp;
        n = n ^ (tmp * tmp);
    }
    printf("%lld
", ans);
    return 0;
}

//2
#include<map>
#include<set>
#include<queue>
#include<cmath>
#include<stack>
#include<ctime>
#include<vector>
#include<cstdio>
#include<string>
#include<cstring>
#include<sstream>
#include<iostream>
#include<algorithm>
#include<unordered_map>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int maxn = 1e6 + 5;
const int MAXM = 3e6;
const ll MOD = 998244353;
const ull seed = 131;
const int INF = 0x3f3f3f3f;

const ll r1 = 262199973, r2 = 736044383, invs17 = 559329360;
int N = 5e4;
ll p1[50005], p2[50005], pp1[50005], pp2[50005];
ll ppow1(int b){
    if(b <= N) return p1[b];
    else return pp1[b / N] * p1[b % N] % MOD;
}
ll ppow2(int b){
    if(b <= N) return p2[b];
    else return pp2[b / N] * p2[b % N] % MOD;
}
ll solve(ll n){
    n = n % (MOD - 1) + MOD - 1;
    return (ppow1(n) - ppow2(n) + MOD) % MOD * invs17 % MOD;
}
void init(){
    p1[0] = p2[0] = 1;
    for(int i = 1; i <= N; i++){
        p1[i] = p1[i - 1] * r1 % MOD;
        p2[i] = p2[i - 1] * r2 % MOD;
    }
    pp1[0] = pp2[0] = 1;
    for(int i = 1; i <= N; i++){
        pp1[i] = pp1[i - 1] * p1[N] % MOD;
        pp2[i] = pp2[i - 1] * p2[N] % MOD;
    }
}
int main(){
    int q;
    ll n;
    init();
    scanf("%d%lld", &q, &n);
    ll ans = 0, tmp;
    for(int i = 1; i <= q; i++){
        tmp = solve(n);
        ans ^= tmp;
        n = n ^ (tmp * tmp);
    }
    printf("%lld
", ans);
    return 0;
}