题解 | #小沙的数数#

H题，这个题呢主要是从二进制加法方面来考虑，首先将m转化为二进制，我们知道异或 的时候两个想异为1那么异或没有办法进位则可以考虑到如果他最大的话那么必定在此处最少有一个1，再来看加法两数相加若得某一位为1则有两种情况一种是这一位仅有1另一种是从后边进位上来在加本位的数，那么若想要异或最大就必须1在本位且只有一个，证明：从第一位开始看要想最大则必定只有一个1否则加法会进到下一位若从后位进上来那么本位也会往前进位后边同理可得，则就将问题转化为了在某一位里选择任意一个位置那么情况有n种即从n个里边选一个假设总共有p个位置有1那么最终得到n^p.得到这个结论还不行因为0<=n<=1e18,则最小的n*n也会爆long long，那么就需要另一种算法名为龟速乘，附代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#define PI acos(-1)
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
inline ll read()
{
	int s = 0, f = 1;
	char ch = getchar();
	while (ch < '0' || ch>'9') {
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		s = s * 10 + ch - '0';
		ch = getchar();
	}
	return s * f;
}

const int mod = 1e9 + 7;
ll n, m;
ll qmul(ll u, ll v)
{
	ll ans = 0;
	while (v)
	{
		if (v % 2) {
			ans = (ans + u) % mod;
		}
		u = (u + u) % mod;
		v >>= 1;
	}
	return ans;
}
int main()
{
	scanf("%lld %lld", &n, &m);
	int cnt = 0;
	while (m)
	{
		if (m & 1) cnt++;
		m /= 2;
	}
	ll ans = 1;
	for (int i = 0; i < cnt; i++)
			ans = qmul(ans, n);
	printf("%lld\n", ans);
	return 0;
}

}