题面链接

https://ac.nowcoder.com/acm/contest/23477/H

题面

思路

根据异或运算的性质我们能知道无论如何组合我们经量想让位为1的数量保持不变，那么我们就将问题转化为了在二进制下m的1的数量，然后再将这些1放进n个位置即可，也就是$ans=n^x$(x表示的是1的数量)

证明

由于在二进制拆位最后同位情况下如果存在不止一个一，那么异或之后的贡献一定小于我们的费用，所以我们要保证对于每一位的个数要么是$0$，要么是$1$，这样的话才能保证$a[xor]=a[+]$，随后我们发现对于每一位来说，他们均不相互干扰，那么他们可能产生的情况便都是n种，所以我们只需要求二进制下$m$有多少个$1$，随后求$n^x$次方即可。

代码

注意直接快速幂要爆精度

#include<bits/stdc++.h>
using namespace std;
//----------------�Զ��岿��----------------
#define ll long long
#define mod 1000000007
#define endl "\n"
#define PII pair<int,int>int dx[4]={0,-1,0,1},dy[4]={-1,0,1,0};ll lowbit(ll x){return -x & x;}const int N = 2e6+10;
//----------------�Զ��岿��----------------ll quick_pow2(ll x, ll n) {ll res = 0;x%= mod;n%= mod;while(n) {if(n & 1) {res = (res + x) % mod;}x = (x%mod + x%mod) % mod;n >>= 1;}return res%mod;
} ll ksm(ll x, ll n) {ll res = 1;while(n > 0) {if(n & 1)    res = quick_pow2(res,x);x = quick_pow2(x,x);n >>= 1;}return res % mod;
}ll n,m;int main()
{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);cin>>n>>m;ll k = 0;for(ll i = 60;i >= 0; --i){if(m & (1LL<<i)) k++;}cout<<ksm(n,k)<<endl;return 0;
}