前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >2019 南昌网络赛 H The Nth Item

2019 南昌网络赛 H The Nth Item

作者头像
用户2965768
发布2019-09-18 10:14:24
5490
发布2019-09-18 10:14:24
举报
文章被收录于专栏:wym

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

本文链接:https://blog.csdn.net/qq_41603898/article/details/100636842

我觉得好假啊。

把if else 位置换了,就过了。还有人预处理前 N 项过的,我矩阵快速幂不服,连1e18数据都没有。

因为有循环节,所以标记,也可以直接找循环节更快。

代码语言:javascript
复制
#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("%s\n",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
*/
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019年09月08日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档