首页 > 其他分享 >老年选手只会做入门题(一)

老年选手只会做入门题(一)

时间:2022-09-01 22:26:35浏览次数:48  
标签:leq10 入门 Nim tt 石子 异或 选手 老年 114514

总共有 \(n\) 组石子 \((n\leq10^6)\) 。
每组石子有 \(M_i\) 堆,每组里面第一堆石子有 \(X_i\) 个,后面 \(M_i-1\) 堆石子每堆的个数比上一堆的个数多 \(1\) 。
对所有石子玩 \(\tt Nim\) 游戏,问 \(\tt Nim\) 游戏结果。

\(n\leq10^6,M_i,X_i\leq10^{16}\)

老年选手只会做这种入门的题目了。
\(\tt Nim\) 游戏就是把所有的石子堆的个数异或起来,看一下最后异或的值是否为零。
发现可以先算出每一组的异或值然后把每一组的异或值异或起来可以得到答案。

打一个表可以发现其实对于每一组的异或值四个为一个循环。
假设 \(X_i=114514\) 的表长这样:

114514 114514
114515 1
114516 114517
114517 0
114518 114518
114519 1
114520 114521
114521 0
114522 114522
114523 1
114524 114525
114525 0
114526 114526
114527 1
114528 114529
114529 0
114530 114530
114531 1
114532 114533
114533 0
114534 114534
114535 1
114536 114537

规律非常显然,然后代码是小学生都会写的东西,不放了。

标签:leq10,入门,Nim,tt,石子,异或,选手,老年,114514
From: https://www.cnblogs.com/Oier-GGG/p/16647982.html

相关文章