专栏首页wym2019 南昌网络赛 H The Nth Item

2019 南昌网络赛 H The Nth Item

版权声明:本文为博主原创文章,遵循 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("%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
*/

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 2019 ICPC 南京网络赛 H-Holy Grail

    As the current heir of a wizarding family with a long history,unfortunately, you...

    风骨散人Chiam
  • 南京网络预选赛 The Preliminary Contest for ICPC Asia Nanjing 2019 H. Holy Grail 多源最短路

    用户2965768
  • 专属| 新型恶意软件“俄罗斯套娃”现身

    近日,安全团队发现恶意攻击者利用GitHub推广后门版应用。所有托管后门应用的账号目前全部移除。恶意应用下载名叫 Supreme NYC Blaze Bot (...

    漏斗社区
  • 2019腾讯浙江文旅数字营销峰会召开 探讨文旅产业转型升级 | 数字文旅周报09期(3.25-3.31)

    ? 2019腾讯浙江文旅数字营销峰会召开 探讨文旅产业转型升级 3月28日,2019浙江文旅数字营销峰会将在杭州香格里拉酒店举行。 本届峰会将邀请腾讯公司...

    腾讯文旅
  • 南昌大学航天杯第二届程序设计竞赛校赛网络同步赛 H小q的数列

    while ((ch = getchar()) >= '0' && ch <= '9'){

    用户2965768
  • 入围名单公布!腾讯云IoT应用创新大赛火爆进行中!

    腾讯云IoT应用创新大赛是腾讯云面向物联网领域举办的大型竞赛,通过腾讯云IoT全链路产品能力,开放平台和服务,与广大开发者共同创新,孵化优秀的IoT产品和解决方...

    腾小云
  • 刷新记录,算法开源!字节跳动获人体姿态估计竞赛双冠 | CVPR 2019

    【导读】6 月 16--20 日,计算机视觉与模式识别领域顶会 CVPR 2019 在美国长滩举行。每年的 CVPR 盛会除了精彩的论文分享、Workshop ...

    AI科技大本营
  • 腾讯携手厦门打造智慧出行新体验 微信刷码坐公交 | 数字文旅周报12期(4.22-4.28)

    ? 腾讯携手厦门打造智慧出行新体验 微信刷码坐公交 4月24日,腾讯公司与厦门公交集团有限公司达成合作,乘车码正式上线厦门公交,为市民游客打造更为高效便捷的绿...

    腾讯文旅
  • 20年后,我们这样看春晚

    小时候,每个除夕夜一家人都会守在小小的彩电之前看春晚。 20年后,小彩电变成大大的液晶显示屏,一家人看着高清直播参与现场互动。 随着视频产品、技术、生态不断的...

    腾讯云音视频

扫码关注云+社区

领取腾讯云代金券