2026 杭电暑期多校 5——括号凸包(判断一个凸包是否合法,由于起点和终点相同,因此我们肯定绕了个圈子,我们要判断的是到底绕了几圈?只需要看这个向量的方位角是否可通过循环位移排成递增即可啊)(方位角递增这个性质,可以通过这个枚举顺序实现,就不要通过增加 dp 状态实现) · znzryb
## 题目大意
### 括号凸包
<!-- Notion block type: heading_4 -->
给定二维平面上的 $n$ 个点,所有点互不相同,且不存在三点共线。每个点上写有一个括号,可能是左括号 $\texttt{(}$ ,也可能是右括号 $\texttt{)}$。
我们称一个字符串 $S$ 是一个合法括号序列,当且仅当它可以由如下递归规则生成:
- 空串是一个合法括号序列;
- 如果 $A$ 是合法括号序列,那么字符串 $\texttt{(}A\texttt{)}$ 也是合法括号序列;
- 如果 $A$ 和 $B$ 都是合法括号序列,那么 $AB$ 也是合法括号序列。
例如,$\texttt{()}$,$\texttt{(())}$,$\texttt{()()}$ 都是合法括号序列,而 $\texttt{)(}$,$\texttt{(()}$,$\texttt{())(}$ 不是合法括号序列。
现在,你需要从给定的点中选出若干个互不相同的点作为顶点,构成一个凸多边形。在本题中,一个由 $m$ 个点 $p_{a_1},p_{a_2},\dots,p_{a_m}$ 构成的多边形被称为凸多边形,当且仅当满足:
- $m \ge 3$;
- 这些点按照 $a_1,a_2,\dots,a_m$ 的顺序依次连接,并连接 $a_m$ 与 $a_1$ 后,形成一个简单多边形(即多边形的边仅在相邻边的端点处相交,不相邻边互不相交);
- 对于该多边形的每一条边,其余所有顶点都严格位于这条边所在直线的同一侧。
换句话说,所选出的点必须恰好按照它们在自身凸包上的环形顺序排列,并且所有内角都严格小于 $180^\circ$,凸多边形上不存在三点共线。
对于一个凸多边形,任选其边界上的一个顶点作为起点,并沿着多边形边界按顺时针或逆时针方向依次遍历所有顶点,最后回到起点前停止。这样可以得到一个长度为 $m$ 的括号序列:若当前顶点上写有左括号,则写下 $\texttt{(}$;若当前顶点上写有右括号,则写下 $\texttt{)}$。
你的任务是找到**包含至少一个左括号**的凸多边形,使得对于该多边形上的**任意一个写有左括号的顶点**,以它作为起点沿多边形边界并以**任意方向**遍历得到的括号序列都是合法括号序列。请计算满足条件的凸多边形个数,并将结果对 $998244353$ 取模后输出。
<!-- Notion block type: heading_4 -->
第一行包含一个整数 $T$($1 \le T \le 100$),表示数据组数。
对于每组数据:
第一行包含一个整数 $n$($1 \le n \le 500$),表示点的数量。
接下来 $n$ 行,每行包含三个整数 $x_i, y_i, t_i$($0 \le x_i, y_i \le 10^9$,$t_i \in \{0, 1\}$),表示第 $i$ 个点的坐标和括号类型。其中 $t_i = 0$ 表示左括号, $t_i = 1$ 表示右括号。
**保证每组数据中所有点互不相同,且不存在三点共线**。
保证所有数据的 $n$ 之和不超过 $1000$。
<!-- Notion block type: heading_4 -->
对于每组数据,输出一行一个整数,表示满足条件的凸多边形方案数对 $998244353$ 取模后的结果。
<!-- Notion block type: heading_4 -->
Plaintext
```
5
4
1 1 0
2 4 1
3 9 0
4 16 1
5
1 1 0
2 4 0
3 9 0
4 16 1
5 25 1
6
47 58 0
30 23 0
27 34 1
35 7 1
10 30 1
1 25 1
8
10 5 0
10 16 0
1 5 0
24 9 0
6 2 0
6 12 0
7 18 1
3 13 1
1
0 0 0
```
<!-- Notion block type: heading_4 -->
Plaintext
```
1
0
1
0
0
```
<!-- Notion block type: heading_4 -->
- **对于第一组样例**:$4$ 个点的坐标形如抛物线 $y=x^2$,因此这 $4$ 个点的任意大小大于等于 $3$ 的子集都能构成凸多边形。这四个点的括号类型依次为 $\texttt{(}$、$\texttt{)}$、$\texttt{(}$、$\texttt{)}$。若选择全部 $4$ 个点构成凸四边形,其顺时针与逆时针的环形括号序列循环节均为 $\texttt{()()}$。无论从第 $1$ 个点(左括号)还是第 $3$ 个点(左括号)出发,按顺时针或逆时针方向生成的字符串均为 $\texttt{()()}$,是合法序列。可以证明,选取其他任何 $3$ 个点构成的三角形均因括号数量为奇数而无法满足条件。因此,方案数为 $1$。
- **对于第二组样例**:给出 $5$ 个点,括号类型依次为 $\texttt{(}$、$\texttt{(}$、$\texttt{(}$、$\texttt{)}$、$\texttt{)}$。经尝试,无法选出任何一个使得“从任意左括号出发、沿任意方向遍历”均产生合法序列的凸多边形。方案数为 $0$。
- **对于第五组样例**:只有 $1$ 个点,无法满足构成凸多边形要求的最少顶点数($m \ge 3$),故方案数为 $0$。
## 思路讲解

首先,题目中有关于括号凸包的表述啊,这个括号串肯定是**形如这个** $()()()()...()()$ **这样子**的形式啊。
因为每个括号串的第一个字符肯定是这个 $($,最后一个字符肯定是 $)$,所有奇数位置必是 $($,这个是因为所有的奇数位置肯定是这个开头(题目中要求每个左括号位置循环移动到开头仍然是合法括号串)。
然后接着就是标题里面的结论啊:
**判断一个凸包是否合法,只需要看这个向量的方位角是否可通过循环位移排成递增即可啊,当然前提是不能 3 点共线**。

那么这个结论实际上是这样子来的啊:



因为我们最终会绕一圈(起点和终点相同),**因此我们其实是在判断,是否多绕了一圈**。
这个**三点不能共线**的规定是用在这个 **dp 转移**里面的。
dp 状态我们先这样子定义,但是这样子:



```cpp
vector<vector<ll> > dp(N, vector<ll>(N));
for (int i = 0; i < N; ++i) {
dp[i][i] = 1;
}
```
这样子会多计算出来一些东西,最后减掉就行啊。
```cpp
for (int i = 0; i < N; ++i) {
ans += dp[i][i];
ans %= mod;
}
// 减掉多余的东西啊
ans -= SZ(vec_ijs) / 2;
ans -= N;
```
具体转移的代码:
```cpp
vector<VecIJ> vec_ijs;
vec_ijs.reserve(N * N);
for (int i = 0; i < SZ(A); ++i) {
for (int j = 0; j < SZ(A); ++j) {
if (i == j) continue;
if (A[i].c != A[j].c) {
auto diff = A[j].p - A[i].p;
vec_ijs.push_back({diff, i, j});
}
}
}
// 进行极角排序(上面重载过 VecIJ 的比较运算符号)
sort(all(vec_ijs));
// 按照边的方位角方向,进行这个转移
for (auto [_,u,v]: vec_ijs) {
for (int src = 0; src < N; ++src) {
dp[src][v] += dp[src][u];
dp[src][v] %= mod;
}
}
```
## AC代码
AC
[https://acm.hdu.edu.cn/contest/view-code?cid=1233&rid=11368](https://acm.hdu.edu.cn/contest/view-code?cid=1233&rid=11368)
::: 源代码
```cpp
// teamname: Gospel_rock
/**
* Problem: 括号凸包
* Contest:
* Judge: HDOJ
* URL: https://acm.hdu.edu.cn/contest/problem?cid=1233&pid=1003
* Created: 2026-08-04 20:20:45
* Author: Gospel_rock
* My blog: https://znzryb.com/
*
* Powered by AutoCp https://github.com/Pushpavel/AutoCp
*/
#include <bits/stdc++.h>
#define all(vec) vec.begin(), vec.end()
#define lson(o) (o << 1)
#define rson(o) (o << 1 | 1)
#define SZ(a) ((long long)a.size())
#define fsp(x) fixed << setprecision(x)
#define debug(x) cerr << "[" << #x << "]" << ": " << x << "\n"
#define cend cerr << "\n---------------------------------------------------\n"
#define cEnd cerr << "\n***************************************************\n"
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
// 不用 M_PI: 后者是 POSIX 扩展, glibc <cmath> 严格模式会 undef
const long double PI = acosl(-1.0);
ll lT, testcase;
/*
*
*/
/*
* 2026-2-3 增加编译器识别 Real 类型功能
* 2026-3-19 增加了从斜率式和一般式构造 Line
* 2026-5-4 几何模板大改(QOJ 784 沉淀):新增 isqrt / sqrtL、cross 三参数重载、polygonSignedArea,reorder_polygon 整体判向,isConvex 加 strict 参数,新增凸多边形直径旋转卡壳
* 2026-5-5 Luogu P16223 沉淀:Point 加 id 字段,convex_diameter 加 n <= 2 退化特判,新增 furthest_pair_of_point
* 2026-5-6 P3187 沉淀:getintersect 加浮点 assert + 显式 (DB) cross,make_convex_hull 加 strict 参数,新增 minimum_rectangle_cover
* 2026-5-11 几何全面模板化:Point / Line 改 template<class T>,T 自动分流 ll / i128 / DB
* 2026-5-12 加入了 Circle 类
* 2026-5-13 加入了 half_plane_cut 和 unique_line_polar_angle_sort,加入了隐式转换和转换方向
* 2026-5-15 加入了 HullMode
*/
// floor(sqrt(n)), n >= 0;二分 + 防溢出
i128 isqrt(i128 n) {
if (n <= 0) return 0;
i128 lo = 0, hi = (i128)2e18; // sqrt(4e36) <= 2e18
while (lo < hi) {
i128 mid = lo + (hi - lo + 1) / 2;
if (mid <= n / mid) lo = mid; // 等价 mid*mid <= n,避免 i128 平方溢出
else hi = mid - 1;
}
return lo;
}
// 统一 sqrt 入口:浮点直接 sqrtl;整数(含 i128)走 isqrt + fraction,避免 (long double) i128 在 n > 2^53 时丢整数精度。
template<typename T>
long double sqrtL(T n) {
if constexpr (is_floating_point_v<T>) {
return sqrtl((long double)n);
} else {
i128 ni = (i128)n;
if (ni <= 0) return 0;
i128 i = isqrt(ni);
long double id = (long double)i;
long double rd = (long double)(ni - i * i);
// sqrt(i^2 + r) = i * sqrt(1 + r/i^2)
return id * sqrtl(1.0L + rd / (id * id));
}
}
// x*x 安全平方: 整数升 i128 防溢出 (1000^2 不会溢, 但模板要扛 1e9 量级输入),
// 浮点原样 T*T 不动 (i128 没浮点意义).
template<class T>
auto squared(T x) {
if constexpr (is_floating_point_v<T>) {
return x * x;
} else {
return (i128)x * (i128)x;
}
}
template<class T>
int sgn(T x) {
if (-eps < x && x < eps) return 0;
return x < 0 ? -1 : 1;
}
template<class T>
struct Point {
T x, y;
int id = -1; // 原始下标. -1 表示派生点 (+ - * 等算术结果) 或未赋值, id 无意义
explicit Point(T x_ = 0, T y_ = 0) : x(x_), y(y_) {
}
// Point<U> -> Point<T> 隐式 (common_type 单调升档方向, U -> T 必须无损):
// common_type_t<U, T> == T 才放行 (例 ll -> DB 通; DB -> ll 拦, 防 truncation)
template<class U, class = enable_if_t<is_same_v<common_type_t<U, T>, T> > >
Point(const Point<U> &o) : x((T)o.x), y((T)o.y), id(o.id) {
}
// 只对左值生效的复合运算符
Point &operator+=(Point p) & {
x += p.x, y += p.y;
return *this;
}
Point &operator-=(Point p) & {
x -= p.x, y -= p.y;
return *this;
}
Point &operator*=(T t) & {
x *= t, y *= t;
return *this;
}
Point &operator/=(T t) & {
x /= t, y /= t;
return *this;
}
Point operator-() const { return Point(-x, -y); }
friend Point operator+(Point a, Point b) { return a += b; }
friend Point operator-(Point a, Point b) { return a -= b; }
// 标量乘除: 返回 Point<common_type_t<T, U>> (C++14), 自动算公共类型
// <ll,ll>=ll / <ll,DB>=DB / <DB,ll>=DB; R==T 走 copy ctor, R!=T 走 converting ctor
template<class U>
friend auto operator*(Point a, U b) {
Point<common_type_t<T, U> > r = a;
r *= b;
return r;
}
template<class U>
friend auto operator*(U a, Point b) {
Point<common_type_t<T, U> > r = b;
r *= a;
return r;
}
template<class U>
friend auto operator/(Point a, U b) {
Point<common_type_t<T, U> > r = a;
r /= b;
return r;
}
friend bool operator<(Point a, Point b) {
int sx = sgn(a.x - b.x);
if (sx != 0) return a.x < b.x;
return a.y < b.y;
}
friend bool operator>(Point a, Point b) { return b < a; }
friend bool operator==(Point a, Point b) {
return sgn(a.x - b.x) == 0 && sgn(a.y - b.y) == 0;
}
friend bool operator!=(Point a, Point b) { return !(a == b); }
friend istream &operator>>(istream &is, Point &p) { return is >> p.x >> p.y; }
friend ostream &operator<<(ostream &os, Point p) { return os << "(" << p.x << ", " << p.y << ")"; }
auto norm() const {
if constexpr (!is_floating_point_v<T>) {
return (__int128_t)x * x + (__int128_t)y * y;
} else {
return x * x + y * y;
}
}
DB abs() const { return sqrtL(norm()); }
Point rot90() const {
return Point(-y, x);
}
Point<DB> rot(DB ang) const {
return Point<DB>(cosl(ang) * x - sinl(ang) * y, sinl(ang) * x + cosl(ang) * y);
}
// L1 范数 (曼哈顿) = |x| + |y|. 整型分支走 __int128_t 防溢出.
auto normL1() const {
auto ax = (x < 0 ? -x : x), ay = (y < 0 ? -y : y);
if constexpr (!is_floating_point_v<T>) {
return (__int128_t)ax + (__int128_t)ay;
} else {
return ax + ay;
}
}
// Linf 范数 (切比雪夫) = max(|x|, |y|). 返回类型与 T 同.
T normLinf() const {
auto ax = (x < 0 ? -x : x), ay = (y < 0 ? -y : y);
return ax > ay ? ax : ay;
}
};
template<class T, class U>
auto cross(Point<T> a, Point<U> b) {
// 在 T 为整数的时候,使用 __int128_t 整型进行计算
//(改为这个非float,那么在类型为I128时,仍然可以计算)
if constexpr (!is_floating_point_v<T> && !is_floating_point_v<U>) {
return (__int128_t)a.x * b.y - (__int128_t)a.y * b.x;
} else {
return a.x * b.y - a.y * b.x;
}
}
// 三点重载: 以 o 为原点, 算 (a - o) × (b - o)
// 用途: 判 3 点 turn (>0 左转, <0 右转, =0 共线) / 2 倍三角形有向面积 / 凸包面积扫描
template<class T, class U, class V>
auto cross(Point<T> o, Point<U> a, Point<V> b) {
return cross(a - o, b - o);
}
template<class T, class U>
auto dot(Point<T> a, Point<U> b) {
// 在 T 为整数的时候,使用 __int128_t 整型进行计算
if constexpr (!is_floating_point_v<T> && !is_floating_point_v<U>) {
return (__int128_t)a.x * b.x + (__int128_t)a.y * b.y;
} else {
return a.x * b.x + a.y * b.y;
}
}
// 三点重载: 以 o 为原点, 算 (a - o) · (b - o)
// 用途: 判夹角钝/直/锐 (>0 锐, =0 直, <0 钝) / 投影长度的有符号 2 倍 / 点在线段上的位置判定
template<class T, class U, class V>
auto dot(Point<T> o, Point<U> a, Point<V> b) {
return dot(a - o, b - o);
}
// 采用两点式
template<class T>
struct Line {
Point<T> p1, p2;
Line() = default;
Line(Point<T> a, Point<T> b) : p1(a), p2(b) {
}
// Line<U> -> Line<T> 隐式 (common_type 单调升档方向, 同 Point converting ctor)
template<class U, class = enable_if_t<is_same_v<common_type_t<U, T>, T> > >
Line(const Line<U> &o) : p1(o.p1), p2(o.p2) {
}
// AC https://qoj.ac/submission/2146870
Line(T k, T c) : p1(Point<T>(0, c)), p2(Point<T>(1, k + c)) {
}
friend bool operator<(Line a, Line b) {
if (a.p1 != b.p1) return a.p1 < b.p1;
return a.p2 < b.p2;
}
friend bool operator==(Line a, Line b) {
if (a.p1 != b.p1) return false;
if (a.p2 != b.p2) return false;
return true;
}
friend istream &operator>>(istream &is, Line &e) {
T a, b, c, d;
is >> a >> b >> c >> d;
e = Line(Point<T>(a, b), Point<T>(c, d));
return is;
}
friend ostream &operator<<(ostream &os, Line l) {
return os << "<" << l.p1 << ", " << l.p2 << ">";
}
};
Line<DB> gen_line_from_general(DB a, DB b, DB c) {
// 方向向量 (b, -a)
Point<DB> p1, p2;
if (b != 0) {
p1 = Point<DB>(0, -c / b);
} else {
p1 = Point<DB>(-c / a, 0);
}
p2 = Point<DB>(p1.x + b, p1.y - a);
return Line<DB>(p1, p2);
}
// 使用这个东西,Point 必须是 double 等浮点类型
template<class T, class U>
Point<DB> project(Point<T> p, Line<U> l) {
Point<DB> vec = l.p2 - l.p1;
// 这个距离反正早除晚除都要除掉
DB r = dot(vec, p - l.p1) / ((DB)vec.x * vec.x + vec.y * vec.y);
return l.p1 + vec * r;
}
template<class T, class U>
Point<DB> reflect(Point<T> p, Line<U> l) {
Point<DB> proj = project(p, l);
return proj + proj - p;
}
mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
constexpr int ON_SEGMENT = 0;
constexpr int COUNTER_CLOCKWISE = 1;
constexpr int CLOCKWISE = -1;
constexpr int ONLINE_BACK = 2;
constexpr int ONLINE_FRONT = -2;
template<class T, class U>
int CCW(Point<T> p, Line<U> l) {
auto a = l.p2 - l.p1;
auto b = p - l.p1;
if (sgn(cross(a, b)) > 0) {
return COUNTER_CLOCKWISE;
}
if (sgn(cross(a, b)) < 0) {
return CLOCKWISE;
}
if (sgn(dot(a, b)) < 0) {
return ONLINE_BACK;
}
if (a.norm() < b.norm()) return ONLINE_FRONT;
return ON_SEGMENT;
}
template<class T, class U>
bool isOrthogonal(Line<T> a, Line<U> b) {
auto c = a.p2 - a.p1, d = b.p2 - b.p1;
return !sgn(dot(c, d));
}
template<class T, class U>
bool isParallel(Line<T> a, Line<U> b) {
auto c = a.p2 - a.p1, d = b.p2 - b.p1;
return !sgn(cross(c, d));
}
template<class T, class U>
bool isSegIntersect(Line<T> a, Line<U> b) {
// 判断线段相交
return CCW(b.p1, a) * CCW(b.p2, a) <= 0 && CCW(a.p1, b) * CCW(a.p2, b) <= 0;
}
// bool isIntersectStrict(Line a,Line b){ // 判断线段相交
// return CCW(b.p1,a)*CCW(b.p2,a)<0 && CCW(a.p1,b)*CCW(a.p2,b)<0;
// }
// p+tv=q+sw
// (p-q) x w+tv x w = 0 (利用叉乘乘以自身为0,消掉sw)
// t=-(p-q)x w/(vxw)
// 传入的是方向式 拿到的是两直线交点
template<class T, class U>
Point<DB> getintersect(const Line<T> &a, const Line<U> &b) {
Point<DB> p = a.p1, v = a.p2 - a.p1, q = b.p1, w = b.p2 - b.p1;
Point<DB> u = p - q;
DB t = (DB)cross(w, u) / cross(v, w);
return p + v * t;
}
// 距离平方(不开方):旋转卡壳里 ans 反复更新,留到最后一次 sqrt
template<class T, class U>
auto distancePPNorm(const Point<T> &a, const Point<U> &b) {
return (a - b).norm();
}
// L2 欧几里得距离 (sqrt 版, 用 long double). 整型坐标走 isqrt + fraction 不丢精度.
template<class T, class U>
DB distancePP(const Point<T> &a, const Point<U> &b) {
return (a - b).abs();
}
// L1 曼哈顿距离 = |dx| + |dy|. 返回类型继承 normL1 (整型 -> __int128_t, 浮点 -> T).
template<class T, class U>
auto distancePPL1(const Point<T> &a, const Point<U> &b) {
return (a - b).normL1();
}
// Linf 切比雪夫距离 = max(|dx|, |dy|). 返回类型 T.
template<class T, class U>
T distancePPLinf(const Point<T> &a, const Point<U> &b) {
return (a - b).normLinf();
}
// 也可以用 project 来算
template<class T, class U>
DB distancePL(Point<T> p, Line<U> l) {
auto val = cross(l.p1, l.p2, p);
return sgn(val) * val / (l.p2 - l.p1).abs();
}
// AC https://qoj.ac/submission/2001668
template<class T, class U>
DB distancePS(Point<T> p, Line<U> l) {
// 避免 distanceSS 调用的时候发生这个退化(即线段退化为了点)
if (l.p1 == l.p2) {
return (p - l.p1).abs();
}
auto t = l.p2 - l.p1;
if (sgn(dot(t, p - l.p1)) < 0) {
return (p - l.p1).abs();
}
if (sgn(dot(t, p - l.p2)) > 0) {
return (p - l.p2).abs();
}
return distancePL(p, l);
}
// AC https://qoj.ac/submission/2001588
template<class T, class U>
DB distanceSS(Line<T> a, Line<U> b) {
if (isSegIntersect(a, b)) return 0;
return min({distancePS(a.p1, b), distancePS(a.p2, b), distancePS(b.p1, a), distancePS(b.p2, a)});
}
// === polar_angle_sort 套件 (espanso :polarAngleSort, 拆自 :Point)
// get_part_of_point + polar_angle_sort(Point) + polar_angle_sort(Line) + unique_line_polar_angle_sort
// 定义获取区域的辅助函数,辅助
template<class T>
int get_part_of_point(const Point<T> &p) {
if (p.y < 0) return 0; // 下半平面 (-pi, 0)
if (p.y == 0 && p.x >= 0) return 1; // 角度为 0 的部分 (含原点)
return 2; // 上半平面 (0, pi]
}
struct PointColor {
Point<ll> p;
int c;
};
struct VecIJ {
Point<ll> d;
int i, j;
bool operator<(const VecIJ &o) const {
auto [parta,partb] = make_tuple(get_part_of_point(d), get_part_of_point(o.d));
if (parta != partb) return parta < partb;
return sgn(cross(d, o.d)) == 1;
}
};
ll N;
void Solve() {
cin >> N;
vector<PointColor> A(N);
for (int i = 0; i < N; ++i) {
cin >> A[i].p >> A[i].c;
}
vector<vector<ll> > dp(N, vector<ll>(N));
for (int i = 0; i < N; ++i) {
dp[i][i] = 1;
}
vector<VecIJ> vec_ijs;
vec_ijs.reserve(N * N);
for (int i = 0; i < SZ(A); ++i) {
for (int j = 0; j < SZ(A); ++j) {
if (i == j) continue;
if (A[i].c != A[j].c) {
auto diff = A[j].p - A[i].p;
vec_ijs.push_back({diff, i, j});
}
}
}
sort(all(vec_ijs));
for (auto [_,u,v]: vec_ijs) {
for (int src = 0; src < N; ++src) {
dp[src][v] += dp[src][u];
dp[src][v] %= mod;
}
}
ll ans = 0;
for (int i = 0; i < N; ++i) {
ans += dp[i][i];
ans %= mod;
}
ans -= SZ(vec_ijs) / 2;
ans -= N;
ans %= mod;
if (ans < 0) ans += mod;
cout << ans << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf); // 无缓冲流,方便我们调试
#endif
cin >> lT;
for (testcase = 1; testcase <= lT; ++testcase)
Solve();
return 0;
}
/*
AC
https://acm.hdu.edu.cn/contest/view-code?cid=1233&rid=11368
*/
```
:::
## 心路历程(WA,TLE,MLE……)