2019 南昌网络赛 H The Nth Item
- 2019 年 10 月 4 日
- 筆記
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/qq_41603898/article/details/100636842
我觉得好假啊。
把if else 位置换了，就过了。还有人预处理前 N 项过的，我矩阵快速幂不服，连1e18数据都没有。
因为有循环节，所以标记，也可以直接找循环节更快。
#include <bits/stdc++.h> #include <cstring> #define ll long long using namespace std; const ll mod = 998244353; const ll loop = 499122176; struct Mat { int n,m; ll mem[2][2]; Mat(int n, int m) { this->n = n, this->m = m; memset(mem, 0, sizeof mem); return; } Mat operator*(const Mat &a)const { Mat c(n,a.m); for (int i = 0; i < c.n; i++) { for (int j = 0; j < c.m; j++) { for (int k = 0; k < m; k++) c.mem[i][j] += mem[i][k] * a.mem[k][j]; c.mem[i][j] %= mod; } } return c; } }; Mat solve(Mat a,Mat c,char *s) { Mat b = c; // printf("%sn",s); for(int i=strlen(s)-1; i>=0; i--) { int cur = s[i] - '0'; while(cur--) b = b*a; Mat tmp = a*a; a = tmp*tmp; a = a*a*tmp; } return b; } ll num; ll cf; map<ll,ll> q; char s[5000]; int main() { ll x0,x1,a,b; ll tmp,loop; Mat m1(2,2),m2(2,2); x0 = 0; x1 = 1; a = 3; b = 2; m1.mem[0][0] = 0; m1.mem[0][1] = b; m1.mem[1][0] = 1; m1.mem[1][1] = a; m2.mem[0][0] = x0; m2.mem[1][0] = 0; m2.mem[0][1] = x1; m2.mem[1][1] = 0; scanf("%lld",&num); scanf("%lld",&cf); ll f1,f2,f3,ans=0,last; for(int i=1; i<=num; i++) { //ltoa(cf,s,10); if(q[cf]==0) { sprintf(s,"%lld",(cf)); m1.mem[0][0] = 0; m1.mem[0][1] = b; m1.mem[1][0] = 1; m1.mem[1][1] = a; m1 = solve(m1,m2,s); last = m1.mem[0][0]; q[cf] = last; ans^=last; cf = cf^(last*last); } else if(q[cf]!=0) { last = q[cf]; cf = cf^(q[last]*q[last]); ans^=last; continue; } } printf("%lld",ans); return 0; } /* 1 1 2 2 1 8 */
