题意
给定长度为 的序列满足 ，定义操作 ：
1
2
3
4
5
6
| S(l,r)=
if r-l>1
S(l,r-1)
S(l+1,r)
else
swap(a[l],a[r])
|
求执行 之后的 。
思路
的递归定义不太本质，不妨直接考虑底层的交换（设 -= 表示相邻两位进行交换），那么 为：
不妨构造 ，过程为：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| 1,4
-=
-=
-=
-=
-=-=
1,6
-=-=
-=-=
-=-=
-=-=
-=-=
-=-=
-= -=
1,8
-= -=
-= -=
-=-=-=-=
|
我们发现对于 ，因为两次向右位移一位，中间的部分会直接抵消。
显然，这样我们只会交换左奇右偶的位置对，那么这样两次都交换就等于没有交换。
这是一个谢尔宾斯基三角形的标准形式，那么我们可以得到下表（行号为 ，右边直接对应交换情况）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
-=
-=-=
-= -=
-=-=-=-=
-= -=
-=-= -=-=
-= -= -= -=
-=-=-=-=-=-=-=-=
-= -=
-=-= -=-=
-= -= -= -=
-=-=-=-= -=-=-=-=
-= -= -= -=
-=-= -=-= -=-= -=-=
-= -= -= -= -= -= -= -=
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
|
那么显然，我们只要求出 附近的一次交换即可得解（对于 为奇数，则可能要两次）。
利用分形的性质，我们定义 表示这个位置是否需要交换：
第一行表示 超出了三角形之外；
第二行表示 落在了整次幂中（此时整一行为 ）；
第三行表示 在左半边，此时上面的三角形与当前三角形是一样的，所以向上走；
第四行表示 在右半边，此时左边的三角形与当前三角形是一样的，所以向左走。
显然，这是一个 的过程。
细节上虽然我们定义的三角形是放大了两倍的，但因为这是一个分形，放大两倍还是自己，所以 无需进行任何处理。
以上纯纯赛时脑子不好使，实际上 减一之后 。
CODE
因为自己 rating 没到 1200 所以没有写代码。
upd 2023/2/17: 补了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| #include<cstdio>
using namespace std;
using ll=long long;
const int FSIZE=1<<20;
ll t,n,k;
char BuF[FSIZE],*InF=BuF;
template<typename T>void read(T &x){
for(;48>*InF||*InF>57;++InF);
for(x=0;47<*InF&&*InF<58;x=x*10+(*InF++^48));
}
bool c(ll n,ll k){
--k;--n;
return(k>=0&&(n&k)==k);
}
void work(){
read(n);read(k);
if(n&1){
if(k&1){
if(c(n-1,k-1)) printf("%lld\n",k-2);
else if(c(n-1,k)) printf("%lld\n",k+1);
else printf("%lld\n",k);
}else{
if(c(n-1,k)){
if(c(n-1,k+1)) printf("%lld\n",k+2);
else printf("%lld\n",k+1);
}else printf("%lld\n",k);
}
}else if(c(n,k)){
if(k&1) printf("%lld\n",k+1);
else printf("%lld\n",k-1);
}else printf("%lld\n",k);
}
int main(){
fread(BuF,1,FSIZE,stdin);
for(read(t);t--;work());
fclose(stdin);
fclose(stdout);
return(0);
}
|