The Nth Item 南昌网络赛（递推数列，分段打表）

比眉伴天荒 2023-08-17 17:04 98阅读 0赞

# The Nth Item #

\\\[ Time Limit: 1000 ms \\quad Memory Limit: 262144 kB \\\]

## 题意 ##

给出递推式，求解每次 \\(F\[n\]\\) 的值，输出所有 \\(F\[n\]\\) 的 \\(xor\\) 值。

## 思路 ##

对于线性递推数列，可以用特征方程求出他的通项公式，比如这题  
\\\[ F\[n\] = 3F\[n-1\]+2F\[n-2\] \\\\ x^2 = 3x+2 \\\\ x = \\frac\{3\\pm \\sqrt\{17\}\}\{2\} \\\]  
令 \\(F\[n\] = C\_1x\_1^n + C\_2x\_2^n\\)  
将 \\(F\[0\]\\) 和 \\(F\[1\]\\) 带入  
\\\[ \\begin\{aligned\} &\\begin\{cases\} C\_1 + C\_2 = 0 \\\\ C\_1\\frac\{3+ \\sqrt\{17\}\}\{2\} + C\_2\\frac\{3- \\sqrt\{17\}\}\{2\} = 1 \\end\{cases\} \\\\ &\\begin\{cases\} C\_1 = \\frac\{1\}\{\\sqrt\{17\}\}\\\\ C\_2 = -\\frac\{1\}\{\\sqrt\{17\}\} \\end\{cases\} \\end\{aligned\} \\\]  
即 \\(F\[n\] = \\frac\{1\}\{\\sqrt\{17\}\} \\left\[\\left(\\frac\{3+\\sqrt\{17\}\}\{2\}\\right)^n - \\left(\\frac\{3-\\sqrt\{17\}\}\{2\}\\right)^n \\right\]\\)

\\(\\sqrt\{17\}\\) 可以通过二次剩余来得到其中一个可能的解，\\(524399943\\) 就是一个解。  
令 \\(p = \\frac\{3+\\sqrt\{17\}\}\{2\}，q=\\frac\{3-\\sqrt\{17\}\}\{2\}\\)，现在的问题就是解出 \\(p^n\\) 和 \\(q^n\\)。  
首先因为 \\(n\\) 高达 \\(1e18\\)，可以利用欧拉降幂，把 \\(n\\) 降到 \\(2mod-1\\) 级别内，也即是 \\(2e9\\) 附近。  
可以利用 \\(n = x\*50000+y\\)，\\(q^n = q^\{x\*50000\} \* q^y\\)，将 \\(q\\) 在 \\(5e4\\) 以内的幂打表出来，在打出 \\(q\\) 的幂为 \\(k\*5e4\\) 的表，然后就可以做到 \\(O(1)\\) 查询。  
对于 \\(q\\) 也是相同的做法。

/*************************************************************** > File Name : a.cpp > Author : Jiaaaaaaaqi > Created Time : Wed 11 Sep 2019 10:01:20 PM CST ***************************************************************/ #include <map> #include <set> #include <list> #include <ctime> #include <cmath> #include <stack> #include <queue> #include <cfloat> #include <string> #include <vector> #include <cstdio> #include <bitset> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #include <unordered_map> #define lowbit(x) x & (-x) #define mes(a, b) memset(a, b, sizeof a) #define fi first #define se second #define pb push_back #define pii pair<int, int> typedef unsigned long long int ull; typedef long long int ll; const int maxn = 1e5 + 10; const int maxm = 1e5 + 10; const ll mod = 998244353; const ll INF = 1e18 + 100; const int inf = 0x3f3f3f3f; const double pi = acos(-1.0); const double eps = 1e-8; using namespace std; ll n, m; int cas, tol, T; ll fpow(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 sqrt17 = 524399943, phiC = mod-1; ll p, q, inv17; ll ppow1[maxn], ppow2[maxn]; ll qpow1[maxn], qpow2[maxn]; void handle() { inv17 = fpow(sqrt17, mod-2); p = 1ll*(3ll+sqrt17)*fpow(2, mod-2)%mod, q = 1ll*(3ll-sqrt17+mod)*fpow(2, mod-2)%mod; ppow1[0] = qpow1[0] = 1; for(int i=1; i<=50000; i++) { ppow1[i] = ppow1[i-1]*p%mod; qpow1[i] = qpow1[i-1]*q%mod; } ppow2[0] = qpow2[0] = 1; ppow2[1] = ppow1[50000]; qpow2[1] = qpow1[50000]; for(int i=2; i<=50000; i++) { ppow2[i] = ppow2[i-1]*ppow1[50000]%mod; qpow2[i] = qpow2[i-1]*qpow1[50000]%mod; } } ll getp(ll n) { return ppow2[n/50000]*ppow1[n%50000]%mod; } ll getq(ll n) { return qpow2[n/50000]*qpow1[n%50000]%mod; } ll solve(ll n) { if(n >= phiC) n = n%phiC+phiC; return inv17*(getp(n)-getq(n)+mod)%mod; } int main() { // freopen("in", "r", stdin); handle(); scanf("%lld%lld", &n, &m); ll ans = 0; for(int i=1; i<=n; i++) { ll tmp = solve(m); m ^= tmp*tmp; ans ^= tmp; } printf("%lld\n", ans); return 0; }

转载于:https://www.cnblogs.com/Jiaaaaaaaqi/p/11509318.html