The 2019 Asia Nanchang First Round Online Programming Contest The Nth Item

The Nth Item

思路：

先用特征根法求出通向公式，然后通向公式中出现了\(\sqrt{17}\)，这个可以用二次剩余求出来，然后可以O(\(log(n)\))求出。

但是还不够，我们先对\(n\)欧拉降幂，然后求base为\(\sqrt{1e9}\)的快速幂，预处理一些东西，就可以类似O(1)求出了。

代码：

#pragma GCC optimize(2)

#pragma GCC optimize(3)

#pragma GCC optimize(4)

#include<bits/stdc++.h>

using namespace std;

#define y1 y11

#define fi first

#define se second

#define pi acos(-1.0)

#define LL long long

//#define mp make_pair

#define pb push_back

#define ls rt<<1, l, m

#define rs rt<<1|1, m+1, r

#define ULL unsigned LL

#define pll pair<LL, LL>

#define pli pair<LL, int>

#define pii pair<int, int>

#define piii pair<pii, int>

#define pdd pair<double, double>

#define mem(a, b) memset(a, b, sizeof(a))

#define debug(x) cerr << #x << " = " << x << "\n";

#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

//head

const int MOD = 998244353;

const LL fsqrt17 = 473844410;

const LL sqrt17 = MOD-fsqrt17;

const LL inv2 = (MOD+1)/2;

const LL invsqrt17 = 438914993;

const int N = 4e4 + 5;

LL p[N], pp[N], P[N], PP[N], q, n;

LL f(LL n) {

    return (p[n%(N-1)]*P[n/(N-1)])%MOD;

}

LL F(LL n) {

    return (pp[n%(N-1)]*PP[n/(N-1)])%MOD;

}

int main() {

    p[0] = pp[0] = 1;

    for (int i = 1; i < N; ++i) p[i] = p[i-1]*(3+sqrt17)%MOD*inv2%MOD, pp[i] = pp[i-1]*(3+fsqrt17)%MOD*inv2%MOD;

    P[0] = PP[0] = 1;

    for (int i = 1; i < N; ++i) {

        P[i] = P[i-1]*p[N-1]%MOD;

        PP[i] = PP[i-1]*pp[N-1]%MOD;

    }

    scanf("%lld %lld", &q, &n);

    LL res = 0;

    for (int i = 1; i <= q; ++i) {

        LL ans = -(f(n%(MOD-1))-F(n%(MOD-1)))*invsqrt17%MOD;

        ans = (ans + MOD) % MOD;

        res ^= ans;

        n ^= ans*ans;

    }

    printf("%lld\n", res);

    return 0;

}

巴特西

The 2019 Asia Nanchang First Round Online Programming Contest The Nth Item

最新文章

热门文章