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;
}
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using i128 = __int128_t;
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
ll mul(ll a, ll b, ll m) {
return (i128)a * b % m;
}
ll qp(ll a, ll b, ll m) {
ll r = 1;
while (b) {
if (b & 1) r = mul(r, a, m);
a = mul(a, a, m);
b >>= 1;
}
return r;
}
bool mr(ll n) {
if (n < 2) return 0;
for (ll p : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) {
if (n % p == 0) return n == p;
}
ll d = n - 1;
int s = 0;
while ((d & 1) == 0) {
d >>= 1;
s++;
}
for (ll a : {2LL, 325LL, 9375LL, 28178LL,
450775LL, 9780504LL, 1795265022LL}) {
if (a % n == 0) continue;
ll x = qp(a % n, d, n);
if (x == 1 || x == n - 1) continue;
bool ok = 0;
for (int i = 1; i < s; i++) {
x = mul(x, x, n);
if (x == n - 1) {
ok = 1;
bre
temp 2026-10-2 21:58:49
YIZHIYANG
aaaluofan
司马只因锥
