#include<cstdio> #include<cmath> #include<iostream> #include<cstring> #include<algorithm> #include<map> #include<vector> using namespace std; typedef long long ll; typedef vector<ll>vec; typedef vector<vec>mat; ll M=998244353; map<ll,ll>cc; mat mul(mat &A,mat &B){ mat C(A.size(),vec(B[0].size())); for(int i=0;i<A.size();i++) for(int k=0;k<B.size();k++) for(int j=0;j<B[0].size();j++) { C[i][j]=(C[i][j]+A[i][k]*B[k][j])%M; } return C; } mat pow(mat A,ll n) { mat B(A.size(),vec(A.size())); for(int i=0;i<A.size();i++) { B[i][i]=1; } while(n>0) { if(n&1) B=mul(B,A); A=mul(A,A); n>>=1; } return B; } map<ll,ll>kkk; int main() { mat A(2,vec(2)); A[0][0]=3,A[0][1]=2,A[1][0]=1,A[1][1]=0; mat B(2,vec(2)); ll q,n; kkk.clear(); scanf("%lld%lld",&q,&n); ll dns=0,k,kk1; while(q--) { B=pow(A,n); ll kk=dns; // cout<<B[1][0]<<‘ ‘<<n<<endl;; dns^=B[1][0]; kkk[n]=B[1][0]; n=n^(B[1][0]*B[1][0]); if(dns==kk1) { if(q%2==1) dns=kk; else dns=kk1; break; } kk1=kk; //cout<<dns<<endl; } printf("%lld\n",dns); }
For a series F:
F(0)=0,F(1)=1F(n)=3∗F(n−1)+2∗F(n−2),(n≥2)?
We have some queries. For each query N, the answer A is the value F(N) modulo 998244353.
Moreover, the input data is given in the form of encryption, only the number of queries Q and the first query N1?are given. For the others, the query Ni?(2≤i≤Q) is defined as the xor of the previous Ni−1? and the square of the previous answer Ai−1?. For example, if the first query N1? is 2, the answer A1? is 3, then the second query N2? is 2 xor (3∗3)=11.
Finally, you don‘t need to output all the answers for every query, you just need to output the xor of each query‘s answer A1? xor A2?...xor AQ?.
The input contains two integers, Q,N, 1 ≤ Q≤107,0 ≤ N≤1018. Q representing the number of queries and N representing the first query.
An integer representing the final answer.
17 473844410
903193081
The Nth Item (The 2019 Asia Nanchang First Round Online Programming Contest)
原文：https://www.cnblogs.com/Shallow-dream/p/11488867.html