Problem B. 纳西妲数列
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
Problem B. 纳西妲数列
时间限制:1s
空间限制:256MB
题目背景
"大慈树王"创造了须弥雨林,又通过教令院将智慧赐予国民。即便她与世长辞,其美名也仍在家喻户晓的故事中传唱。对比起全知全能的大慈树王,纳西妲自认还远远担不起"智慧之神"的名号,对国家的治理也是教令院更加驾轻就熟,她的存在并没有那么大的意义 。所以她在净善宫的每一刻都不停在学习,希望尽快成长为一位合格的神明 。
某天她在学习斐波那契数列,看到在自然中各种事物都存在这个数列,感叹于该数列的神奇。在纳西妲的观点中,万事万物都存在着相互联系。于是她将斐波那契数列中的加法关系更改成异或关系,希望也能在某些事物上发现这个关系。不过在此之前,她想求出这个数列任意一项的值。
题目描述
我们将这个数列命名为 纳西妲数列 ( Nahida sequence ),纳西妲是这样定义这个数列的:
\(f(0) = a\);
\(f(1) = b\);
\(f(n) = f(n-1) \oplus f(n-2), n > 1\) (其中 \(\oplus\) 为按位异或\(^\dagger\) )
\(^\dagger\)按位异或:按位异或运算符\(\oplus\)是双目运算符。其功能是参与运算的两数各对应的二进位相异或。只要对应的两个二进制位不同,结果位就为 \(1\) ,否则就为 \(0\) 。例如 \(1 \oplus 14\)=\((0001)_2 \oplus (1110)_2\)= \((1111)_2\) = \(15\) 。
在 C/C++ 中, 可以使用 ^ 来计算异或,即可以用 a ^ b 来计算 \(a \oplus b\) 的值。
现在给你三个整数 \(a, b, n\) ,你能求出 \(f(n)\) 吗?
为了研究规律,你需要回答 \(T\) 组独立的测试数据。
输入格式
第一行一个整数 \(T\) , 代表 \(T\) 组测试数据。
接下来 \(T\) 行,每行三个整数 \(a, b, n\) 。
输出格式
对于每个测试数据,输出 \(f(n)\) 的值,占一行。
输入样例1
2
3 5 2
10 18 20
输出样例1
6
24
样例1解释
在一组测试数据中,\(3 \oplus 5 = 6\),所以答案为 \(6\).
输入样例2
见xor2.in
输出样例2
见xor2.out
数据范围与限制
测试点编号 | 约定 | 测试点分值 |
---|---|---|
\(1\) | \(n = 2\) | 每个测试点10分 |
\(2\) | \(a = b, 0 \le n \le 10^4\) | 每个测试点10分 |
\(3 \sim 4\) | \(0 \le n \le 10^4\) | 每个测试点10分 |
\(5 \sim 10\) | 无特殊约定 | 每个测试点10分 |
对于所有测试点,\(1 \le T \le 10^3\),\(0 \le a,b,n \le 10^9\).
2023秋 苏州青少年科技馆(吴江计算机协会)CSP-J/S模拟赛(3)
- 状态
- 已结束
- 规则
- OI
- 题目
- 4
- 开始于
- 2023-10-11 18:30
- 结束于
- 2023-10-11 21:00
- 持续时间
- 2.5 小时
- 主持人
- 参赛人数
- 34