小沙的数数（组合数学+位运算）

题面链接

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

题面

思路

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

证明

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

代码

注意直接快速幂要爆精度

#include
using namespace std;
//----------------�Զ��岿��----------------
#define ll long long
#define mod 1000000007
#define endl "\n"
#define PII pair

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