专栏文章

小 S 的 ARC191 参赛记-2

AARIS2_0
AT_arc191_b题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@miqdk9lh
此快照首次捕获于
2025/12/04 03:03
3 个月前
此快照最后确认于
2025/12/04 03:03
3 个月前
查看原文
前序：小 S 的 ARC191 参赛记-1（即 ARC191A 题解）
切掉了 A 后，小 S 十分愉快地开了 B。

大致题意

给定 n,kn,k，求第 kk 大的 满足 x mod n=x⊕nx\bmod n=x\oplus n 的 xx，无解输出 −1-1，多测。
小 S 看到这道题也是十分兴奋啊，想了一下立马口胡了个结论：
  • 当 x<nx<n 或 xx 二进制下的最高位高于 nn 二进制下的最高位时，没有一个 xx 满足条件。
因为这是题解不是赛时，所以小 S 还是要证一下的。
首先，x<nx<n 时，原式变为 x=x⊕nx=x\oplus n，很明显当且仅当 n=0n=0 时成立，而 nn 显然不能为 00。
其次，如果 xx 二进制下的最高位高于 nn 二进制下的最高位时，那么有 x⊕n>nx\oplus n>n（因为 xx 二进制下的最高位会被保留），而 x mod n<nx\bmod n<n，所以原式不成立。
那么，因为 x≥nx\ge n 且 xx 的二进制下的最高位不高于 nn 二进制下的最高位时，所以有 n≤x<2×nn\le x<2\times n，则 x mod n=x−nx\bmod n=x-n。
那也就是说，如果 nn 在二进制下某位是 11，则 xx 在二进制下这位也必须是 11，不然无法实现 x−n=x⊕nx-n=x\oplus n。
小 S 高兴的不得了，因为他发现，这意味着 xx 在二进制下，可以自由变化的那些位置，恰好就是 nn 的二进制下不大于最高位的、值为 00 的位数。设这样的位数有 sumsum 个，则有 2sum2^{sum} 个不同的 xx。
至于如何计算第 kk 大的 xx，将 k−1k-1 二进制拆分之后一位位填到 sumsum 个自由位上去就可以了。
于是小 S 愉快地无伤通过了此题，真是与 ARC189B 的 -10 截然不同的结局啊。
也许，这就是小 S 每天殷切地对着卫星许愿的原因吧。
S.A.T.E.L.L.I.T.E.
（但是小 S 还是被 C 的神秘结论创飞了）

Code

CPP
#include<algorithm>
#include<bitset>
#include<deque>
#include<iomanip>
#include<iostream>
#include<iterator>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<utility>
#include<vector> 
#include<chrono>
#include<random>
#include<tuple>
#include<unordered_map>
using namespace std;
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define debug1(x) cerr<<#x<<"="<<x<<" "
#define debug2(x) cerr<<#x<<"="<<x<<"\n"
const int inf=1e16,maxn=1e6+10;
namespace ARIS2_0{
    void solve(){
        int n,k;cin>>n>>k;
        vector<int>v;
        for(int i=0;(1ll<<i)<=n;i++){
            if(!((n>>i)&1))v.push_back(i);
        }
        if(k>(1ll<<(v.size()))){
            cout<<"-1\n";
            return;
        }
        int ans=n;
        k--;
        for(int i=0;i<v.size();i++){
            if((k>>i)&1){
                k-=(1ll<<i);
                ans+=(1ll<<(v[i]));
            }
        }
        cout<<ans<<"\n";
    }
}
signed main(){
    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t;cin>>t;
    while(t--)ARIS2_0::solve();
	return 0;
}
/*
clang++ -std=c++14 -Wall -Wextra -Wshadow -Wconversion -Wl,-stack_size -Wl,512000000
*/

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...