n 和 k 最大都是 109，因此指数 nk 最大为 1018，必须使用 long long 保存。
不需要利用费马小定理缩小指数。快速幂的循环次数只有
O(log(nk)),
可以直接处理 1018 级别的指数。
参考实现
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll md = 1000000007;
ll qp(ll a, ll b) {
ll r = 1;
while(b) {
if(b & 1) r = r * a % md;
a = a * a % md;
b >>= 1;
}
return r;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll n, k;
cin >> n >> k;
cout << qp(2, n * k) << '\n';
return 0;
}
/*
题意：求所有线段子集的并集连通块数量之和。
思路：每个连通块由左端点最小的线段唯一代表。扫描端点，当遇到第 k 个左端点时，
已有 c 条线段完全结束。让当前线段成为新连通块起点的方案数为 2^(c+n-k)。
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int mod=1000000007;
int l[200005];
int r[200005];
ll pw[100005];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
int x,y;
cin >> x >> y;
l[x] = 1;
r[y] = 1;
}
pw[0] = 1;
for (int i = 1; i <= n; i++)
pw[i] = pw[i - 1] * 2 % mod;
ll ans = 0;
int c = 0;
int k = 0;
for (int i = 1; i <= 2 * n; i++) {
if (l[i]) {
k++;
ans = (ans + pw[c + n - k]) % mod;
}
if (r[i]) c++;
}
cout << ans;
return 0;
}
i = 4, lowbit(4) = 4
节点 4 管辖 [1,4]
i = 6, lowbit(6) = 2
节点 6 管辖 [5,6]
i = 7, lowbit(7) = 1
节点 7 管辖 [7,7]
i = 8, lowbit(8) = 8
节点 8 管辖 [1,8]
因此我们可以让：
mxi 表示节点 i 管辖区间内的最大值；
mni 表示节点 i 管辖区间内的最小值。
建树时，把每个位置 i 的身高加入所有包含它的树状数组节点中。
查询 [l,r] 时，从右端点 r 开始向左拆区间。
如果当前节点 r 管辖的整段区间：
[r−lowbit(r)+1,r]
完全在 [l,r] 内，就可以直接使用 mxr 和 mnr，然后跳过这一整段。
如果这段区间越过了左边界 l，就不能整段使用，只能单独处理当前位置 r，然后令 r 减 1。
这样就能把一个询问区间拆成若干个树状数组已经维护好的区间，再合并最大值和最小值。
以询问 [1,5] 为例：
[1,5] 可以拆成 [5,5] 和 [1,4]
其中：
节点 5 管辖 [5,5]
节点 4 管辖 [1,4]
所以只需要用这两个节点的信息，就能得到整个区间的最大值和最小值。
这道题没有修改操作，所有身高一开始就确定，所以用树状数组维护静态区间最值是可以的。
参考实现
#include<bits/stdc++.h>
using namespace std;
const int N = 50005;
const int INF = 1e9;
int n, q;
int a[N], mx[N], mn[N];
int lb(int x) {
return x & -x;
}
void add(int x, int v) {
for (int i = x; i <= n; i += lb(i)) {
mx[i] = max(mx[i], v);
mn[i] = min(mn[i], v);
}
}
int gmx(int l, int r) {
int res = 0;
while (r >= l) {
if (r - lb(r) + 1 >= l) {
res = max(res, mx[r]);
r -= lb(r);
} else {
res = max(res, a[r]);
r--;
}
}
return res;
}
int gmn(int l, int r) {
int res = INF;
while (r >= l) {
if (r - lb(r) + 1 >= l) {
res = min(res, mn[r]);
r -= lb(r);
} else {
res = min(res, a[r]);
r--;
}
}
return res;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> q;
for (int i = 1; i <= n; i++) mn[i] = INF;
for (int i = 1; i <= n; i++) {
cin >> a[i];
add(i, a[i]);
}
while (q--) {
int l, r;
cin >> l >> r;
cout << gmx(l, r) - gmn(l, r) << '\n';
}
return 0;
}
要把 4 个变量的枚举变成 2 个，突破口在路径的结构上。
我们要走的路径是 1→A→B→C→D→1。它是一个首尾相接的对称环。如果在中间切一刀，把 B 和 C 当作桥墩确定下来，整个过程就被劈成了左半边 1→A→B 和右半边 C→D→1。
一旦 B 被外层循环固定，给它找前驱 A 的任务只和 B 与 1 有关；一旦 C 固定，找后继 D 的任务只和 C 与 1 有关。这两半是解耦的，把它们拆开分别处理，这就是折半枚举的核心动机。
于是思路变成了：双重循环枚举 B 和 C。对于每一个可能作为桥墩的节点，提前帮它把所有能作为 A 或者 D 的候选点找出来。
为了让总分最大，预处理时可以直接挑分数最大的那个候选点吗？
题目规定 4 个点必须互不相同，直接贪心选最大的容易翻车。假设预处理时只给每个点记录了分数第一的候选点，当外层循环枚举到具体的 B 和 C 时，万一 B 记录的那个最强 A 恰好就是 C，或者恰好和 D 撞了位置，唯一的备选就失效了，这条路直接作废。
算一下具体的排斥情况：给 B 找 A 的时候，A 需要避让的“竞争者”最多只有三个，分别是当前的 B、当前的 C、以及 C 选出来的 D。
在最极端的冲突下，分数第一大的备选被 C 占了，第二大的备选被 D 占了，那么第三大的备选就一定是个自由身。也就是说，在预处理阶段，只要把满足连通条件的备选点按分数从大到小排个序，只存前 3 个，就足以应付所有位置重合的极端情况。
通过维护前 3 大这个常数级的操作，既完美避开了去重的雷区，又不需要增加多余的循环层数，将复杂度彻底锁在了 O(N2)。
参考实现
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int n, m, k;
ll val[2505];
vector<int> g[2505];
int ok[2505][2505];
int dis[2505];
int bst[2505][5];
void bfs(int s) {
for (int i = 1; i <= n; ++i) {
dis[i] = -1;
}
dis[s] = 0;
queue<int> q;
q.push(s);
while (!q.empty()) {
int u = q.front();
q.pop();
if (dis[u] == k + 1) continue;
for (int v : g[u]) {
if (dis[v] == -1) {
dis[v] = dis[u] + 1;
q.push(v);
}
}
}
for (int i = 1; i <= n; ++i) {
if (dis[i] != -1 && dis[i] <= k + 1) {
ok[s][i] = 1;
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m >> k;
for (int i = 2; i <= n; ++i) {
cin >> val[i];
}
for (int i = 1; i <= m; ++i) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
for (int i = 1; i <= n; ++i) {
bfs(i);
}
for (int i = 2; i <= n; ++i) {
vector<int> tmp;
for (int j = 2; j <= n; ++j) {
if (i != j && ok[1][j] && ok[j][i]) {
tmp.push_back(j);
}
}
sort(tmp.begin(), tmp.end(), [&](int x, int y) {
return val[x] > val[y];
});
int sz = tmp.size();
for (int j = 0; j < 3 && j < sz; ++j) {
bst[i][j] = tmp[j];
}
}
ll ans = 0;
for (int i = 2; i <= n; ++i) {
for (int j = 2; j <= n; ++j) {
if (i == j || !ok[i][j]) continue;
for (int x = 0; x < 3; ++x) {
int a = bst[i][x];
if (!a || a == j) continue;
for (int y = 0; y < 3; ++y) {
int d = bst[j][y];
if (!d || d == i || d == a) continue;
ans = max(ans, val[a] + val[i] + val[j] + val[d]);
}
}
}
}
cout << ans << '\n';
return 0;
}
定义状态 dp[l][r][p] 表示在区间 [l,r] 内，准确使用 p 个乘号所能获得的最大结果。
当区间长度大于 1 时，枚举一个分割点 m 将当前区间分为 [l,m] 和 [m+1,r]。假设左半部分分配了 c 个乘号，那么两部分合并的运算方式有两种可能：
若两段区间由加号连接，那么右半部分需要使用 p - c 个乘号，此时结果为左右部分最大值之和。
若两段区间由乘号连接，那么连接本身消耗了一个乘号，右半部分就只能使用 p - 1 - c 个乘号，此时结果为左右部分最大值的乘积。
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll dp[20][20][20];
ll a[20];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 0; i < 20; i++) {
for (int j = 0; j < 20; j++) {
for (int p = 0; p < 20; p++) {
dp[i][j][p] = -1;
}
}
}
for (int i = 1; i <= n; i++) {
dp[i][i][0] = a[i];
}
for (int len = 2; len <= n; len++) {
for (int l = 1; l <= n - len + 1; l++) {
int r = l + len - 1;
for (int m = l; m < r; m++) {
for (int p = 0; p <= k && p <= r - l; p++) {
for (int c = 0; c <= p; c++) {
if (dp[l][m][c] != -1 && dp[m + 1][r][p - c] != -1) {
dp[l][r][p] = max(dp[l][r][p], dp[l][m][c] + dp[m + 1][r][p - c]);
}
}
if (p > 0) {
for (int c = 0; c <= p - 1; c++) {
if (dp[l][m][c] != -1 && dp[m + 1][r][p - 1 - c] != -1) {
dp[l][r][p] = max(dp[l][r][p], dp[l][m][c] * dp[m + 1][r][p - 1 - c]);
}
}
}
}
}
}
}
cout << dp[1][n][k] << "\n";
return 0;
}
YIZHIYANG初来乍到 2026-7-26 11:24:11