题解：致敬传奇捆绑测试题目 Perm
来自不知道什么时候的回忆。给定正整数 \(n\) ，一个 \(1\sim n\) 的排列 \(p\) 是一个好排列，当且仅当使得对于任意 \(1\le k<n\) ，都有 \(\sum_{i=1}^k p_i > p_{k+1}\) 。现在请你求出字典序第 小的好排列 \(p\) 。\(1\le n\le 10^6\) ，\(1\le k\le 10^{18}\) 。可是你出这个题开 Subtask 放 corner 被喷爆了……
你突然惊醒，发现你不仅只会 \(k=1\) ，而且还需要搞一场联测的 T1。这次你决定不绑 Subtask，而是一次把所有问题问完。
设 \(a_{l,i}\) 为对于 \(n=l,k=1\) 的上述问题答案的第 \(i\) 个数字，请你求出 \(\oplus_{1\le j\le i\le n}(a_{i,j}+j)\) ，其中 \(\oplus\) 代表按位异或。
Input
一行一个正整数 \(n\) 。
Output
一行一个整数表示答案。
Note
对于 \(60\%\) 的数据，保证 \(n\le 10^6\) 。
对于所有数据，保证 \(1\le n\le 10^{18}\) 。
分析
\(O(n)\) 部分分做法
手动模拟 \(k=1\) 的排列 \(p\)，发现：
\[n=1,p_1 = 1 \]\[n=2,p_2 = 2,1 \]\[n=3,p_3 = 3,1,2 \]\[n=4,p_4 = 3,1,2,4 \]\[n=5,p_5 = 3,1,2,4,5 \]\[... \]\[p_n = 3,1,2,4,5,...,n \]\(p_3\) 之后每次只会在排列末尾新加入 \(n\) 以保证最小字典序。
排列 \(p\) 每一项加上 \(j\) 得到最后统计答案的排列 \(p'\) :
统计答案时从第一项到最后一项被异或的次数由 \(n\) 递减，根据异或的性质只有被异或奇数次的会统计到答案里，判一下奇偶性即可。时间复杂度 \(O(n)\) ，可以通过 \(60\%\) 数据 。
\(O(1)\) 做法
利用 \(O(n)\) 做法打表，得到：
\[n=1,ans = 2 \]\[n=2\sim 9,ans = 2,0,10,10,6,4,22,22 \]\[n=10\sim 17,ans =2,0,26,26,6,4,38,38 \]\[n=18\sim 25,ans = 2,0,42,42,6,4,54,54 \]\[... \]发现除开 \(n=1\) 其后每 \(8\) 个数一组存在规律且满足一次函数关系。直接 \(O(1)\) 算就完了。
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {
ll otto = 0;
char a = getchar();
while(!isdigit(a)) a = getchar();
while(isdigit(a)) {
otto = (otto << 1) + (otto << 3) + (a ^ 48);
a = getchar();
}
return otto;
}
void solve(ll n) {
if(n == 1) {
printf("2");
}
else {
--n;
int op = n % 8;
if(op == 1) printf("2");
if(op == 2) printf("0");
if(op == 3) printf("%lld", 10 + 16 * (n / 8));
if(op == 4) printf("%lld", 10 + 16 * (n / 8));
if(op == 5) printf("6");
if(op == 6) printf("4");
if(op == 7) printf("%lld", 22 + 16 * (n / 8));
if(op == 0) printf("%lld", 22 + 16 * (n / 8));
}
}
int main() {
freopen("perm.in", "r", stdin);
freopen("perm.out", "w", stdout);
solve(read());
}