hanghangakioi
考试的时候在乱猜结论,交了几遍就过了,证明当然是赛后才想的()
文中加粗部分是需要读者稍微思考一下原因的地方 (不是重点)。
先考虑一下样例二,将 \(10^{18}\) 化成二进制:\(1101...001000000000000000000\)。
其实只需要知道末尾有 \(18\) 个 \(0\) 就行了,因为在 \(x\) 变为 \(x^{2c}\) 时,后面 \(18\) 个 \(0\) 就会变成 \(18\times 2c\) 个 \(0\),如果再异或 \(c\),就相当于把末尾的几位变成 \(c\),此时除了末尾上的 \(c\),\(x^{2c}\oplus c\) 的前面部分的数已经不会影响结果了(因为最后求 \(\operatorname{lowbit}\) 就只关心末几位的值)。所以每做一次操作,末几位都是 \(c\),那么最后的 \(\operatorname{lowbit}\) 就是 \(\operatorname{lowbit}(c)\)。
再扩展到一般情况:
-
\(c\) 是偶数,\(a\) 是奇数,那么二进制中的最后一位就始终都是 \(1\),所以最后的 \(\operatorname{lowbit}\) 就是 \(1\)。
-
\(c\) 是偶数,\(a\) 是偶数,这个就和样例二差不多:\(a\) 的二进制末尾至少有一个 \(0\),\(a^{2c}\) 的末尾就至少有 \(2c\) 个 \(0\),肯定比 \(c\) 的二进制的位数多,异或 \(c\) 就相当于把末尾的几位变成 \(c\),又因为 \(c\) 是偶数,所以 \(a^{2c}\oplus c\) 的末尾也至少有一个 \(0\),又变成了开始的情况,只不过末几位是 \(c\) 而不是 \(a\)。一直推下去,最后的 \(\operatorname{lowbit}\) 就是 \(\operatorname{lowbit}(c)\)。
-
\(c\) 是奇数,此时根据 \(a\) 的奇偶又分成两种情况:
- \(a\) 是偶数,和前面一样:\(a^{2c}\) 的末尾至少有 \(2c\) 个 \(0\),异或 \(c\) 就相当于把末尾的几位变成 \(c\),因为我们只关心末几位,所以就可以把原数看成 \(c\)。
- \(a\) 是奇数,那么 \(a^{2c}\) 也是奇数,因为 \(c\) 也是奇数,奇数异或奇数就变成了偶数,然后又变成了上一个情况,即奇偶交替。
- 如果最后的数是个奇数,那么 \(\operatorname{lowbit}\) 就是 \(1\)。
- 如果最后是个偶数,那么就要考虑倒数第二步。因为 \(b>1\),所以倒数第二步的数的二进制末尾一定是 \(c\),那么最后答案就相当于 \(\operatorname{lowbit}(c^{2c}\oplus c)\)。
其实做到这就已经做完了,但是 \(\operatorname{lowbit}(c^{2c}\oplus c)\) 还可以化简一下。
考虑用二项式定理展开 \(c^{2c}\):
\[c^{2c}=(c-1+1)^{2c}=\sum_{i=0}^{2c} C_{2c}^{i}\times (c-1)^i=1+2c(c-1)+C_{2c}^{2}\times (c-1)^2+...+(c-1)^{2c} \]我们将上式所有项按 \(\operatorname{lowbit}\) 大小来排序,最小的两项当然是 \(1\) 和 \(2c(c-1)\),因为 \(c-1\) 是偶数,所以 \(\operatorname{lowbit}(2c(c-1))=\operatorname{lowbit}(c-1)\times 2\)
从第三项开始,所有项的 \(\operatorname{lowbit}\) 都不小于 \(\operatorname{lowbit}(c-1)\times 2\),所以 \(c^{2c}\) 一定可以被表示为 \(k\times \operatorname{lowbit}(2(c-1))+1\),其中 \(k\in N^+\)。
形象点,把 \(c^{2c}\) 和 \(c\) 的二进制分别表示出来(随便一个例子,只需要看后五位):
\(c^{2c}\):\(1101...1010001\)
\(c\): \(\ \ 1010...0101001\)
可以发现,最末尾的 \(1\) 会抵消,但倒数第二位不会,所以 \(\operatorname{lowbit}(c^{2c}\oplus c)=\operatorname{lowbit}(c-1)\)。
#include <iostream>
#include <cstdio>
#define ll long long
using namespace std;
ll a,b,c;
ll lb(ll x){return x&-x;}
int main()
{
cin >> a >> b >> c;
if(c&1)
{
if((a&1)^(b&1))cout << 1; //ab不同奇偶,那么最后答案就是奇数
else cout << lb(c-1); //ab同奇偶,最后答案就是偶数
}
else cout << ((a&1)?1:lb(c));
return 0;
}
标签:UFO,题解,奇数,Wdoi,末尾,偶数,2c,operatorname,lowbit
From: https://www.cnblogs.com/max0810/p/18329546