20241021 校测T1 致敬传奇捆绑测试题目（Perm） 题解

题解：致敬传奇捆绑测试题目 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'\) :

\[p'=4,3,5,8,10,...,2n \]

统计答案时从第一项到最后一项被异或的次数由 \(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());
}