题目一 ： a^b

思路 ： 快速幂的模版

运行3ms 396KB

inline void solve() {
	ll a = read(), b = read(), p = read();
	ll res = 1;
	while (b) {
		if (b & 1) res = res * a % p;
		b >>= 1;
		a = a * a % p;
	}
	writen(res % p);
}

题目二 ： Raising Modulo Numbers

思路 ： 快速幂的模版

运行14ms 432KB

inline void solve() {
    ll M = read(), n = read(), res = 0;
    mod = M;
    for (int i = 1; i <= n; i ++ ) {
        ll a = read(), b = read();
        res += qmi(a, b);
    }
    writen(res % mod);
}

题目三 ： 64位整数乘法

思路 ： 快速幂的思想 ， 将 b 进行二进制转换 ， 右移一位时将 a 乘 2 即可

运行3ms 396KB

inline void solve() {
	ll a = read(), b = read(), p = read(), res = 0;
	while (b) {
		if (b & 1) res = (res + a) % p;
		b >>= 1;
		a = a * 2 % p;
	}
	writen(res);
}

题目四 ： 最短Hamilton路径

思路 ： 经典的旅行商问题 ， 进行状态dp

运行692ms 164580KB

const int N = 20, M = 1 << N;
ll dp[M][N], w[N][N];
inline void solve() {
	ll n = read();
	for (int i = 0; i < n; i ++ ) {
		for (int j = 0; j < n; j ++ ) {
			w[i][j] = read();
		}
	}
	memset(dp, 0x3f, sizeof dp);
	dp[1][0] = 0;
	for (int i = 0; i < 1 << n; i ++ ) {
		for (int j = 0; j < n; j ++ ) {
			if (i >> j & 1) {
				for (int k = 0; k < n; k ++ ) {
					if (i - (1 << j) >> k & 1) {
						dp[i][j] = min(dp[i][j], dp[i - (1 << j)][k] + w[k][j]);
					}
				}
			}
		}
	}
	writen(dp[(1 << n) - 1][n - 1]);
}

题目五 ： 起床困难综合症

思路 ： 共有的一个性质 ： 每次操作只会影响有关位上的数字 。

log2 (1e9) < 30 ， 所以可以从 29 位开始依次判断能不能取 1

赋 a1 为 0 ， a2 = -1 分别记录进行所有操作后的值 （a2 相当于 a1 所有位取反）

则 a1 位上为 1 的值 ， 我们就可以在 res 上加上 1 ， 或者 a2 位上为 1 的值， 我们也可以加上 1

运行11ms 512KB

ll n, m, res, d, a1, a2 = -1;
string op;
inline void solve() {
	n = read(); m = read();
	for (int i = 1; i <= n; i ++ ) {
		op = sread();
		d = read();
		if (op[1] == 'A') a1 &= d, a2 &= d;
		if (op[1] == 'O') a1 |= d, a2 |= d;
		if (op[1] == 'X') a1 ^= d, a2 ^= d;
	}
	for (int i = 1 << 29; i; i >>= 1) {
		if (a1 & i) res += i;
		else if (a2 & i && i <= m) res += i, m -= i;
	}
	writen(res);
}