problem1 link
$N+1$到$M$ 之间的数字要包含所有1到$N$之间出现的质因子的最高幂即可。
problem2 link
从第一个节点到第$N$个节点依次考虑。对于第$i$个节点来说，其颜色为$j$时，可以选择与前面的连边或者不连边，方案数为$1+(i-1)+g(i-1,j)$。其中$g(x,y)$ 表示前$x$个节点中，颜色为$y$ 的节点的个数
所以节点$i$的方案数为$f(i)=sum_{j=1}^{K}(1+i-1-g(i-1,j))=K*i-sum_{j=1}^{K}g(i-1,j)=K*i-(i-1)=$
$K+(K-1)(i-1)$
所以最后的答案为:
$ans=prod_{i=1}^{N}f(i)$
$=prod_{i=1}^{N}(K+(K-1)(i-1))$
$=prod_{i=0}^{N-1}(K+(K-1)i)$
$=prod_{j=0}^{min(M-1,N-1)}(K+(K-1)j)^{frac{N-1-j}{M}+1}$
最后一步是由于$[1,N]$之间的数字模$M$会出现循环。
problem3 link
相连的顶点会把整个区间分成若干段。预处理四个数组：
(1) $L[i][j]$表示[i,j]是一段，这一段距离左端点最远的点的距离
(2) $R[i][j]$表示[i,j]是一段，这一段距离右端点最远的点的距离
(3) $S[i][j]$表示[i,j]是一段，这一段中距离最远的两点之间的距离
(4)$D[i][j]$表示这一段左右两个端点的距离
然后二分答案。设为$mid$.设 $dp[i][j]$表示已经把$j$对顶点连了起来，最后一对是在$i$的位置时以$i$作为路径的结尾的最小值。那么每次新连一对的时候，要保证前面不能出现大于$mid$的情况。
code for problem1
#include <algorithm>
#include <vector>
using namespace std;
class MissingLCM {
public:
int getMin(int N) {
if (N == 1) {
return 2;
}
long long result = 0;
std::vector<bool> tags(N + 1, false);
for (int i = 2; i <= N; ++i) {
if (!tags[i]) {
for (int j = i + i; j <= N; j += i) {
tags[j] = true;
}
long long t = 1;
while (t <= N / i) {
t *= i;
}
result = std::max(result, N % t == 0 ? N + t : N / t * t + t);
}
}
return static_cast<int>(result);
}
};
code for problem2
class ColorfulLineGraphs {
public:
int countWays(long long N, long long K, int M) {
long long result = 1;
for (int i = 0; i < M && i < N; ++i) {
long long x = K + (K - 1) * i;
long long y = (N - 1 - i) / M + 1;
result = result * Pow(x, y, M) % M;
}
return static_cast<int>(result);
}
private:
long long Pow(long long x, long long y, int M) {
x %= M;
long long result = 1;
while (y != 0) {
if (y % 2 == 1) {
result = result * x % M;
}
x = x * x % M;
y /= 2;
}
return result;
}
};
code for problem3
#include <algorithm>
#include <cstring>
#include <vector>
constexpr int kMaxN = 200;
int L[kMaxN][kMaxN];
int R[kMaxN][kMaxN];
int S[kMaxN][kMaxN];
int D[kMaxN][kMaxN];
int dp[kMaxN][kMaxN + 1];
class BridgeBuilding {
public:
int minDiameter(const std::vector<int> &a, const std::vector<int> &b, int K) {
int n = static_cast<int>(a.size()) + 1;
std::vector<int> prefix_a(n);
std::vector<int> prefix_b(n);
for (int i = 1; i < n; ++i) {
prefix_a[i] = prefix_a[i - 1] + a[i - 1];
prefix_b[i] = prefix_b[i - 1] + b[i - 1];
}
auto Dist = [&](int a, int b, int t) {
if (a >= b) {
return 0;
}
return t == 0 ? prefix_a[b] - prefix_a[a] : prefix_b[b] - prefix_b[a];
};
auto GetMax = [&](int left, int right) {
int number = right - left;
auto Get = [&](int k) {
if (k <= number) {
return Dist(left, left + k, 0);
}
return Dist(left, right, 0) + Dist(right - (k - number), right, 1);
};
int total = Dist(left, right, 0) + Dist(left, right, 1);
int tmax = 0;
for (int L = 0, R = 0; L < number * 2; ++L) {
if (R <= L) {
R = L + 1;
}
int t = Get(L);
while (R < number * 2 && Get(R) - t < total / 2) {
int p = Get(R) - t;
tmax = std::max(tmax, std::min(p, total - p));
++R;
}
int p = Get(R) - t;
tmax = std::max(tmax, std::min(p, total - p));
}
return tmax;
};
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
int s0 = Dist(i, j, 0);
int s1 = Dist(i, j, 1);
D[i][j] = std::min(s0, s1);
S[i][j] = GetMax(i, j);
L[i][j] = R[i][j] = 0;
for (int k = i; k <= j; ++k) {
L[i][j] =
std::max(L[i][j], std::min(Dist(i, k, 0), Dist(k, j, 0) + s1));
L[i][j] =
std::max(L[i][j], std::min(Dist(i, k, 1), Dist(k, j, 1) + s0));
R[i][j] =
std::max(R[i][j], std::min(Dist(k, j, 0), Dist(i, k, 0) + s1));
R[i][j] =
std::max(R[i][j], std::min(Dist(k, j, 1), Dist(i, k, 1) + s0));
}
}
}
auto Check = [&](int mid) {
memset(dp, -1, sizeof(dp));
for (int i = 0; i < n; ++i) {
if (prefix_a[i] + prefix_b[i] <= mid) {
dp[i][1] = std::max(prefix_a[i], prefix_b[i]);
}
}
for (int i = 0; i < n; ++i) {
for (int j = 1; j < K; ++j) {
if (dp[i][j] != -1) {
for (int k = i + 1; k < n; ++k) {
if (S[i][k] <= mid && dp[i][j] + L[i][k] <= mid) {
int v = std::max(R[i][k], dp[i][j] + D[i][k]);
if (dp[k][j + 1] == -1 || dp[k][j + 1] > v) {
dp[k][j + 1] = v;
}
}
}
}
}
}
int result = std::numeric_limits<int>::max();
for (int i = K - 1; i < n; ++i) {
if (dp[i][K] != -1 && Dist(i, n - 1, 0) + Dist(i, n - 1, 1) <= mid) {
result = std::min(result, dp[i][K] + std::max(Dist(i, n - 1, 0),
Dist(i, n - 1, 1)));
}
}
return result <= mid;
};
int result = std::numeric_limits<int>::max();
int left = 0, right = result;
while (left <= right) {
int mid = (left + right) >> 1;
if (Check(mid)) {
result = std::min(result, mid);
right = mid - 1;
} else {
left = mid + 1;
}
}
return result;
}
};