B. 我们苏生自最初的泪滴（tear）
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
题目描述
有一个 个点的完全图，结点编号为 ，结点 之间有权值为 的无向边。
请你求出这个图的最大生成树的大小，对 取模。
输入格式
本题有多组测试数据，第一行一个整数 代表数据组数。
接下来 行，每行一个整数 代表点数。
输出格式
共 行，每行一个整数代表一组数据的答案。
样例输入
9
10
1000
100000
10000000
1000000000
100000000000
10000000000000
1000000000000000
100000000000000000
样例输出
422
499008694
4172096327
3128649679
2692599804
194024000
2969759816
505684415
3052141644
数据规模
本题保证数据随机生成，有子任务限制
- 对于 的数据，。
- 对于 的数据，。
- 对于 的数据，。
- 对于 的数据，。
- 对于 的数据，。
- 对于 的数据，
方便起见，这里提供一份 PollardRho 分解质因数的代码，不使用该模板导致的其他问题不承担责任，使用此代码时请使用 c++20 提交。
代码
namespace pollardrho
{
// #include <bits/stdc++.h>
#define fir first
#define sec second
#define mkp make_pair
#define mkt make_tuple
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned int;
using ldb = long double;
using i128 = __int128_t;
using u128 = __uint128_t;
using pii = pair<int, int>;
using pil = pair<int, i64>;
using pli = pair<i64, int>;
using vi = vector<int>;
using vpii = vector<pii>;
namespace
{
bool Mbe;
constexpr int MOD = 998244353;
template <typename T>
T Norm(T a, T p = MOD) { return (a % p + p) % p; }
template <typename T>
bool cmax(T &a, T b) { return a < b ? a = b, true : false; }
template <typename T>
bool cmin(T &a, T b) { return a > b ? a = b, true : false; }
template <typename T>
T DivFloor(T a, T b) { return a >= 0 ? a / b : (a - b + 1) / b; }
template <typename T>
T DivCeil(T a, T b) { return a >= 0 ? (a + b - 1) / b : a / b; }
namespace FastIO
{
constexpr int LEN = 1 << 20;
char in[LEN + 1], out[LEN + 1];
char *pin = in, *pout = out, *ein = in, *eout = out + LEN;
char gc() { return pin == ein && (ein = (pin = in) + fread(in, 1, LEN, stdin), ein == in) ? EOF : *pin++; }
void pc(char c)
{
pout == eout && (fwrite(out, 1, LEN, stdout), pout = out);
(*pout++) = c;
return;
}
struct Flush
{
~Flush()
{
fwrite(out, 1, pout - out, stdout);
pout = out;
return;
}
} _flush;
template <typename T>
T Read()
{
T x = 0;
int f = 1;
char ch = gc();
while (ch < '0' || ch > '9')
f = (ch == '-' ? (~f + 1) : f), ch = gc();
while (ch >= '0' && ch <= '9')
x = (x << 1) + (x << 3) + (ch ^ 48), ch = gc();
return x * f;
}
void Read(char *s)
{
char ch = gc();
while (ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t')
ch = gc();
while ((ch != EOF) && !(ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t'))
*s = ch, s++, ch = gc();
*s = '\0';
return;
}
template <typename T>
void Read(T &x)
{
x = Read<T>();
return;
}
template <typename T, typename... Args>
void Read(T &x, Args &...args)
{
Read(x), Read(args...);
return;
}
template <typename T>
void Write(T x)
{
static char stk[40];
int tp = 0;
if (x < 0)
pc('-'), x = ~x + 1;
do
stk[tp++] = x % 10 + 48, x /= 10;
while (x);
while (tp--)
pc(stk[tp]);
return;
}
void Write(char ch)
{
pc(ch);
return;
}
void Write(const char *s)
{
while (*s != '\0')
pc(*s), s++;
return;
}
void Puts(const char *s)
{
Write(s), pc('\n');
return;
}
template <typename T, typename... Args>
void Write(T x, Args... args)
{
Write(x), Write(args...);
return;
}
}
using namespace FastIO;
void YES(bool f = true)
{
f ? Puts("YES") : Puts("NO");
return;
}
void NO(bool f = true)
{
YES(!f);
return;
}
void Yes(bool f = true)
{
f ? Puts("Yes") : Puts("No");
return;
}
void No(bool f = true)
{
Yes(!f);
return;
}
void yes(bool f = true)
{
f ? Puts("yes") : Puts("no");
return;
}
void no(bool f = true)
{
yes(!f);
return;
}
template <class U0, class U1>
struct Montgomery
{
constexpr static unsigned B0 = sizeof(U0) * 8U;
U0 n, nr, rs, np;
constexpr Montgomery(const U0 &Mod)
{
SetMod(Mod);
}
constexpr U0 GetMod() const noexcept
{
return n;
}
constexpr void SetMod(const U0 &Mod)
{
assert(Mod >= 2), assert(Mod % 2 == 1);
assert((Mod >> (B0 - 2)) == 0);
n = nr = Mod, rs = -static_cast<U1>(n) % n;
for (u32 i = 0; i < __lg(B0); i++)
{
nr *= 2 - n * nr;
}
np = Reduce(static_cast<U0>(1), rs);
}
constexpr U0 Reduce(const U0 &x) const noexcept
{
const U0 q = x * nr;
const U0 m = (static_cast<U1>(q) * n) >> B0;
return n - m;
}
constexpr U0 Reduce(const U0 &x, const U0 &y) const noexcept
{
const U1 t = static_cast<U1>(x) * y;
const U0 c = t, d = t >> B0;
const U0 q = c * nr;
const U0 m = (static_cast<U1>(q) * n) >> B0;
return d + n - m;
}
constexpr U0 Reduce(const U0 &x, const U0 &y, const U0 &z) const noexcept
{
const U1 t = static_cast<U1>(x) * y;
const U0 c = t, d = t >> B0;
const U0 q = c * nr;
const U0 m = (static_cast<U1>(q) * n) >> B0;
return z + d + n - m;
}
constexpr U0 val(const U0 &x) const noexcept
{
const u64 t = Reduce(x);
return (t == n) ? static_cast<U0>(0) : t;
}
constexpr U0 zero() const noexcept
{
return static_cast<U0>(0);
}
constexpr U0 one() const noexcept
{
return np;
}
constexpr U0 raw(const U0 &x) const noexcept
{
return Reduce(x, rs);
}
template <class U>
requires std::unsigned_integral<U>
constexpr U0 trans(const U &x) const noexcept
{
if (__builtin_expect(x < n, 1))
{
return raw(x);
}
return Reduce(x % n, rs);
}
template <class S>
requires std::signed_integral<S>
constexpr U0 trans(S x) const noexcept
{
if (__builtin_expect(0 <= x && x < static_cast<S>(n), 1))
{
return Raw(x);
}
if ((x %= static_cast<S>(n)) < 0)
{
(x += static_cast<S>(n)) %= static_cast<S>(n);
}
return Reduce(x, rs);
}
constexpr U0 neg(const U0 &x) const noexcept
{
return (x != 0) ? (2 * n - x) : x;
}
constexpr U0 inc(const U0 &x) const noexcept
{
return add(x, np);
}
constexpr U0 dec(const U0 &x) const noexcept
{
return sub(x, np);
}
constexpr U0 add(const U0 &x, const U0 &y) const noexcept
{
return (x + y >= 2 * n) ? (x + y - 2 * n) : (x + y);
}
constexpr U0 sub(const U0 &x, const U0 &y) const noexcept
{
return (x < y) ? (x - y + 2 * n) : (x - y);
}
constexpr U0 mul(const U0 &x, const U0 &y) const noexcept
{
return Reduce(x, y);
}
constexpr U0 mul_add(const U0 &x, const U0 &y, const U0 &z) const noexcept
{
return Reduce(x, y, z);
}
constexpr bool same(const U0 &x, const U0 &y) const noexcept
{
const U0 dif = x - y;
return (dif == 0) || (dif == n) || (dif == -n);
}
};
constexpr bool Is_Prime(u64 x) noexcept
{
if (x <= 1)
{
return false;
}
if (x % 2 == 0)
{
return x == 2;
}
constexpr array<u64, 10> Base{2, 7, 61, 2, 325, 9375, 28178, 450775, 9780504, 1795265022};
const u32 s = __builtin_ctzll(x - 1);
const u64 d = (x - 1) >> s;
const int q = 63 ^ __builtin_clzll(d);
const Montgomery<u64, u128> Mod(x);
const u32 l = (x >> 32) ? 3 : 0;
const u32 r = (x >> 32) ? 10 : 3;
for (u32 _ = l; _ < r; _++)
{
u64 base = Base[_];
if (base % x == 0)
{
continue;
}
base = Mod.trans(base);
u64 a = base;
for (int i = q - 1; ~i; i--)
{
a = Mod.mul(a, a);
if ((d >> i) & 1)
{
a = Mod.mul(a, base);
}
}
if (Mod.same(a, Mod.one()))
{
continue;
}
for (u32 t = 1; t < s && !Mod.same(a, x - Mod.one()); ++t)
{
a = Mod.mul(a, a);
}
if (!Mod.same(a, x - Mod.one()))
{
return false;
}
}
return true;
}
template <bool sorted>
vector<u64> Factorize(u64 n)
{
// vector<pair<u64, u32>> ans;
vector<u64> ans;
if (n % 2 == 0)
{
u32 z = __builtin_ctzll(n);
// ans.push_back({2ULL, z}), n >>= z;
ans.push_back(2ULL), n >>= z;
}
auto upd = [&](const u64 &x)
{
for (auto p : ans)
{
if (x == p)
{
// ++c;
return;
}
}
// ans.push_back({x, 1});
ans.push_back(x);
};
auto Pollard_Rho = [&](const u64 &n)
{
if (n % 2 == 0)
{
return 2ULL;
}
const Montgomery<u64, u128> Mod(n);
const u64 C1 = 1, C2 = 2, M = 512;
u64 Z1 = 1, Z2 = 2, ans = 0;
auto find = [&]()
{
u64 z1 = Z1, z2 = Z2;
for (u64 k = M;; k *= 2)
{
const u64 x1 = z1 + n, x2 = z2 + n;
for (u64 j = 0; j < k; j += M)
{
const u64 y1 = z1, y2 = z2;
u64 q1 = 1, q2 = 2;
z1 = Mod.mul_add(z1, z1, C1), z2 = Mod.mul_add(z2, z2, C2);
for (u64 i = 0; i < M; ++i)
{
u64 t1 = x1 - z1, t2 = x2 - z2;
z1 = Mod.mul_add(z1, z1, C1), z2 = Mod.mul_add(z2, z2, C2);
q1 = Mod.mul(q1, t1), q2 = Mod.mul(q2, t2);
}
q1 = Mod.mul(q1, x1 - z1), q2 = Mod.mul(q2, x2 - z2);
const u64 q3 = Mod.mul(q1, q2), g3 = std::gcd(n, q3);
if (g3 == 1)
{
continue;
}
if (g3 != n)
{
ans = g3;
return;
}
const u64 g1 = std::gcd(n, q1);
const u64 g2 = std::gcd(n, q2);
const u64 C = g1 != 1 ? C1 : C2;
const u64 x = g1 != 1 ? x1 : x2;
u64 z = g1 != 1 ? y1 : y2;
u64 g = g1 != 1 ? g1 : g2;
if (g == n)
{
do
{
z = Mod.mul_add(z, z, C);
g = std::gcd(n, x - z);
} while (g == 1);
}
if (g != n)
{
ans = g;
return;
}
Z1 += 2, Z2 += 2;
return;
}
}
};
do
{
find();
} while (!ans);
return ans;
};
auto DFS = [&](auto &&self, const u64 &n) -> void
{
if (Is_Prime(n))
{
return upd(n);
}
u64 d = Pollard_Rho(n);
self(self, d), self(self, n / d);
};
if (n > 1)
{
DFS(DFS, n);
}
if constexpr (sorted)
{
sort(ans.begin(), ans.end());
}
return ans;
}
}
}
这里还有一份适用于 c++14 版本的代码：
代码
namespace pollardrho
{
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned int;
using u128 = __uint128_t;
namespace
{
template <class U0, class U1>
struct Montgomery
{
constexpr static unsigned B0 = sizeof(U0) * 8U;
U0 n, nr, rs, np;
constexpr Montgomery(const U0 &Mod) { SetMod(Mod); }
constexpr U0 GetMod() const noexcept { return n; }
constexpr void SetMod(const U0 &Mod)
{
// assert(Mod >= 2), assert(Mod % 2 == 1);
// assert((Mod >> (B0 - 2)) == 0);
n = nr = Mod, rs = -static_cast<U1>(n) % n;
for (u32 i = 0; i < __lg(B0); i++)
{
nr *= 2 - n * nr;
}
np = Reduce(static_cast<U0>(1), rs);
}
constexpr U0 Reduce(const U0 &x) const noexcept
{
const U0 q = x * nr;
const U0 m = (static_cast<U1>(q) * n) >> B0;
return n - m;
}
constexpr U0 Reduce(const U0 &x, const U0 &y) const noexcept
{
const U1 t = static_cast<U1>(x) * y;
const U0 c = t, d = t >> B0;
const U0 q = c * nr;
const U0 m = (static_cast<U1>(q) * n) >> B0;
return d + n - m;
}
constexpr U0 Reduce(const U0 &x, const U0 &y, const U0 &z) const noexcept
{
const U1 t = static_cast<U1>(x) * y;
const U0 c = t, d = t >> B0;
const U0 q = c * nr;
const U0 m = (static_cast<U1>(q) * n) >> B0;
return z + d + n - m;
}
constexpr U0 val(const U0 &x) const noexcept
{
const u64 t = Reduce(x);
return (t == n) ? static_cast<U0>(0) : t;
}
constexpr U0 zero() const noexcept { return static_cast<U0>(0); }
constexpr U0 one() const noexcept { return np; }
constexpr U0 raw(const U0 &x) const noexcept { return Reduce(x, rs); }
template <class U, typename std::enable_if<std::is_unsigned<U>::value, int>::type = 0>
constexpr U0 trans(const U &x) const noexcept
{
if (__builtin_expect(x < n, 1))
return raw((U0)x);
return Reduce((U0)(x % n), rs);
}
template <class S, typename std::enable_if<std::is_signed<S>::value, int>::type = 0>
constexpr U0 trans(S x) const noexcept
{
if (__builtin_expect(0 <= x && x < static_cast<S>(n), 1))
return raw((U0)x);
x %= static_cast<S>(n);
if (x < 0)
x += static_cast<S>(n);
return Reduce((U0)x, rs);
}
constexpr U0 neg(const U0 &x) const noexcept { return (x != 0) ? (2 * n - x) : x; }
constexpr U0 inc(const U0 &x) const noexcept { return add(x, np); }
constexpr U0 dec(const U0 &x) const noexcept { return sub(x, np); }
constexpr U0 add(const U0 &x, const U0 &y) const noexcept { return (x + y >= 2 * n) ? (x + y - 2 * n) : (x + y); }
constexpr U0 sub(const U0 &x, const U0 &y) const noexcept { return (x < y) ? (x - y + 2 * n) : (x - y); }
constexpr U0 mul(const U0 &x, const U0 &y) const noexcept { return Reduce(x, y); }
constexpr U0 mul_add(const U0 &x, const U0 &y, const U0 &z) const noexcept { return Reduce(x, y, z); }
constexpr bool same(const U0 &x, const U0 &y) const noexcept
{
const U0 dif = x - y;
return (dif == 0) || (dif == n) || (dif == -n);
}
};
constexpr bool Is_Prime(u64 x) noexcept
{
if (x <= 1)
{
return false;
}
if (x % 2 == 0)
{
return x == 2;
}
constexpr array<u64, 10> Base{2, 7, 61, 2, 325, 9375, 28178, 450775, 9780504, 1795265022};
const u32 s = __builtin_ctzll(x - 1);
const u64 d = (x - 1) >> s;
const int q = 63 ^ __builtin_clzll(d);
const Montgomery<u64, u128> Mod(x);
const u32 l = (x >> 32) ? 3 : 0;
const u32 r = (x >> 32) ? 10 : 3;
for (u32 _ = l; _ < r; _++)
{
u64 base = Base[_];
if (base % x == 0)
{
continue;
}
base = Mod.trans(base);
u64 a = base;
for (int i = q - 1; ~i; i--)
{
a = Mod.mul(a, a);
if ((d >> i) & 1)
{
a = Mod.mul(a, base);
}
}
if (Mod.same(a, Mod.one()))
{
continue;
}
for (u32 t = 1; t < s && !Mod.same(a, x - Mod.one()); ++t)
{
a = Mod.mul(a, a);
}
if (!Mod.same(a, x - Mod.one()))
{
return false;
}
}
return true;
}
vector<u64> Factorize(u64 n)
{
vector<u64> ans;
if (n % 2 == 0)
{
u32 z = __builtin_ctzll(n);
ans.push_back(2ULL), n >>= z;
}
auto upd = [&](const u64 &x)
{
for (auto p : ans)
{
if (x == p)
return;
}
ans.push_back(x);
};
auto Pollard_Rho = [&](const u64 &n)
{
if (n % 2 == 0)
return 2ULL;
const Montgomery<u64, u128> Mod(n);
const u64 C1 = 1, C2 = 2, M = 512;
u64 Z1 = 1, Z2 = 2, ans = 0;
auto find = [&]()
{
u64 z1 = Z1, z2 = Z2;
for (u64 k = M;; k *= 2)
{
const u64 x1 = z1 + n, x2 = z2 + n;
for (u64 j = 0; j < k; j += M)
{
const u64 y1 = z1, y2 = z2;
u64 q1 = 1, q2 = 2;
z1 = Mod.mul_add(z1, z1, C1), z2 = Mod.mul_add(z2, z2, C2);
for (u64 i = 0; i < M; ++i)
{
u64 t1 = x1 - z1, t2 = x2 - z2;
z1 = Mod.mul_add(z1, z1, C1), z2 = Mod.mul_add(z2, z2, C2);
q1 = Mod.mul(q1, t1), q2 = Mod.mul(q2, t2);
}
q1 = Mod.mul(q1, x1 - z1), q2 = Mod.mul(q2, x2 - z2);
const u64 q3 = Mod.mul(q1, q2), g3 = __gcd(n, q3);
if (g3 == 1)
{
continue;
}
if (g3 != n)
{
ans = g3;
return;
}
const u64 g1 = __gcd(n, q1);
const u64 g2 = __gcd(n, q2);
const u64 C = g1 != 1 ? C1 : C2;
const u64 x = g1 != 1 ? x1 : x2;
u64 z = g1 != 1 ? y1 : y2;
u64 g = g1 != 1 ? g1 : g2;
if (g == n)
{
do
{
z = Mod.mul_add(z, z, C);
g = __gcd(n, x - z);
} while (g == 1);
}
if (g != n)
{
ans = g;
return;
}
Z1 += 2, Z2 += 2;
return;
}
}
};
do
{
find();
} while (!ans);
return ans;
};
auto DFS = [&](auto &&self, const u64 &n) -> void
{
if (Is_Prime(n))
return upd(n);
u64 d = Pollard_Rho(n);
self(self, d), self(self, n / d);
};
if (n > 1)
DFS(DFS, n);
sort(ans.begin(), ans.end());
return ans;
}
}
}
云斗学院 2026 省选计划系列模拟赛 #3
- Status
- Done
- Rule
- OI
- Problem
- 3
- Start at
- 2026-1-16 0:00
- End at
- 2026-1-18 20:00
- Duration
- 5 hour(s)
- Host
-
shijingyao
- Partic.
- 86
京公网安备 11011102002149号