[练习记录] 《算法竞赛进阶指南》打卡活动

shiranui / 2023-05-03 / 原文

89. a^b

题目大意

给 \(a,b,p\) 求 \(a^b \mod p\)。

思路

可以直接快速幂。当模数 \(p\) 为 \(1\) 的时候特判一下。

代码

ll a, b, mod;
ll qpow(ll a, ll b) {
	ll res = 1;
	while (b) {
		if (b & 1) res = res * a % mod;
		a = a * a % mod, b >>= 1;
	}
	return res;
}
int main() {
	a = read(), b = read(), mod = read();
	if (mod == 1) printf("0\n");
	else printf("%lld\n", qpow(a, b));
	return 0;
}

AcWing 90. 64位整数乘法

题目大意

给 \(a,b,p\) 求 \(a \times b \mod p\)。

思路1

好像是想让我写龟速乘，但是我直接 __int128 莽过去了（）。

代码1

__int128 a, b, mod;
void prt(__int128 x) {
    if (x > 9) prt(x / 10);
    putchar(x % 10 + '0');
}
int main() {
	a = read(), b = read(), mod = read();
    __int128 ans = a * b % mod;
    prt(ans);
	return 0;
}

思路2

龟速乘，长得和快速幂很像。

代码2

ll a, b, mod;
ll mul(ll a, ll b) {
    ll res = 0;
    while (b) {
        if (b & 1) res = (res + a) % mod;
        a = (a << 1) % mod, b >>= 1;
    }
    return res;
}
int main() {
	a = read(), b = read(), mod = read();
    printf("%lld\n", mul(a, b));
	return 0;
}

91. 最短Hamilton路径

题目大意

给一张 \(n\) 个点的带权无向完全图，求从 \(1\) 到 \(n\) 恰好经过所有点 \(1\) 次的路径的最短长度。

思路

注意到 \(n\leq 20\)，考虑状压dp。

设状态 \(f_{i,s}\) 表示经过了状态为 \(s\) 的点，目前在点 \(i\) 处的路径的最短长度。

那么转移很显然 \(f_{j,s|(1<<j)}=\min(f_{j,s|(1<<j)},f_{i,s}+e_{i,j})\)，其中 \(i\) 在 \(s\) 状态中被访问过，\(j\) 没有。

代码

const int N = 21, INF = 0x3f3f3f3f;
int n, a[N][N];
int f[N][1 << N];
int main() {
    n = read();
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            a[i][j] = read();
    memset(f, 0x3f, sizeof(f));
    f[1][1] = 0;
    for (int s = 0; s < 1 << n; s++)
        for (int i = 1; i <= n; i++) {
            if ((s & (1 << (i - 1))) == 0) continue;
            for (int j = 1; j <= n; j++) {
                if (s & (1 << (j - 1)) == 1) continue;
                f[j][s | (1 << (j - 1))] = min(f[j][s | (1 << (j - 1))], f[i][s] + a[i][j]);
            }
        }
    printf("%d\n", f[n][(1 << n) - 1]);
	return 0;
}