Znzryb's Blog

2026 杭电春季联赛 2——1005-守矢晨风（扫描线维护的激活集合可以应用差分思想，这样只需要维护一个前缀激活集合即可）

Posted on 2026-03-31 Edited on 2026-04-06

题目大意

题目描述

给定平面上 $n$ 个圆形区域，第 $i$ 个圆的圆心坐标为 $(p_i, q_i)$ ，半径为 $r_i$ （保证 $r_i \le 30$ ）。

给定 $m$ 次询问，每次询问给出一个四边平行于坐标轴的矩形区域，指定了其左下角顶点坐标 $(x_{i,1}, y_{i,1})$ 和右上角顶点坐标 $(x_{i,2}, y_{i,2})$ 。对于每次询问，需要计算出在给定的 $n$ 个圆中，有多少个圆与该矩形区域存在至少一个公共点。

数据范围

测试用例数量 $t$ 满足 $1 \le t \le 1000$ 。
每次测试中的圆的个数 $n$ 满足 $1 \le n \le 1.5 \times 10^6$ ，询问的个数 $m$ 满足 $1 \le m \le 10^4$ 。
对于全部测试用例，保证 $\sum n \le 3 \times 10^6$ ， $\sum m \le 2 \times 10^4$ 。
坐标与半径范围： $1 \le p_i, q_i \le 10^9$ ， $1 \le r_i \le 30$ ， $1 \le x_{i,1} \le x_{i,2} \le 10^9$ ， $1 \le y_{i,1} \le y_{i,2} \le 10^9$ 。

样例输入

样例输出

样例解释

在第一组测试数据中，共有 $4$ 个圆和 $1$ 次询问。询问给定的矩形左下角坐标为 $(2, 2)$ ，右上角坐标为 $(6, 4)$ 。经过判断，该矩形与输入的第 $2$ 个圆、第 $3$ 个圆以及第 $4$ 个圆（总计三个圆形）存在公共点，因此该次询问的答案为 $3$ 。第二组测试数据同理，分别输出对应矩形内包含公共点的圆的数量。

思路讲解

这道题目应该是一道扫描线+树状数组，应该是不需要用到这个 K-D 树这种比较高级的东西的。

呃，那我们怎么做这道题目呢？首先就是用这个数据结构，快速求解出大矩形中的这个点，所谓的大矩形，就是矩形和圆的 minkowski 和（这个 minkowski 和是一个圆角矩形），当然，圆角矩形让我们用数据结构处理实在是，我们忽略其圆角，得到的就是所谓的“大矩形”（即图中黑色框框住的部分）。

小羊-2025-12-04-M. Ahmad’s Dish（圆和正多边形的这个 minkowski 和）（minkowski 和的交换不变性）

2025 United Kingdom and Ireland Programming Contest (UKIEPC 2025) 2025 英国 ICPC——B. Brickwork（判断砖块是否重叠）（扫描线的本质就是遍历一个出一个）（维护一个当前生效的集合）（把二维的问题变为一维的问题来做）

okay，我们上面的这个对扫描线总结的比较好。扫描线的重点就是维护一个当前生效的这个集合。按照一顺序排序后，那么我们其实就是要维护一个目前生效的圆的集合。

首先呢，就是这道题目，因为半径比较少，我们不妨把这个不同半径的圆分开处理。

然后因为我们目前把不同的半径分开处理，我们目前可以假设，所有的圆的这个半径都是相同的。我们就是像上面一样，把这个矩形扩大这个半径（👆想上面那个黑色的矩形一样）。

~~然后我们把矩形先按照 x 的右端点排序，再按照 x 的左端点排序~~。不过，我们发现，无论你怎么排序这个矩形和这个点（也就是这个圆心嘛），都很难维护一个严格生效的这个点的集合，主要也是矩形的是一个这个区间范围，无论怎么排都比较麻烦。

不过我们采用差分思想？其实就是如下方法：

左查询：在 $X = X_{min} - 1$ 的时刻，查询树状数组中 $[Y_{min}, Y_{max}]$ 区间的点数，记为 $A$ ，从答案中减去 $A$ 。（记录权重为 $-1$ ）

右查询：在 $X = X_{max}$ 的时刻，查询树状数组中 $[Y_{min}, Y_{max}]$ 区间的点数，记为 $B$ ，加到答案中。（记录权重为 $+1$ ）

采用如上👆方法，我们只需要维护一个 $[-INF,idx]$ 的生效点集合就可以了，可以说是非常轻松惬意了，我们也不需要删除。

然后我们要进行这个几何点的这个扣除：

只要像上面👆一样，不断的枚举这个 dx，就可以排除掉所有的这个不合法的点。


struct Solve {
    ll N, M;
    Compress_<ll> li_y;
    vector<vector<X_y> > r_xy_ls;
    vector<Event> events_backup;
    vector<int> Ans;

    vector<Event> gen_event(ll r) {
        // vector<Event> tmp_events;
        vector<Event> events;
        // tmp_events.reserve(SZ(r_xy_ls[r]));
        for (auto [x,y]: r_xy_ls[r]) {
            events.push_back({x, y, Insert});
        }
        for (auto e: events_backup) {
            e.y1 -= r;
            e.y2 += r;
            if (e.type == Left) {
                e.x -= r;
            } else if (e.type == Right) {
                e.x += r;
            }
            events.push_back(e);
        }
        sort(all(events));
        return events;
    }

    void solve_single_r(ll r) {
        BIT tr(li_y.size());
        sort(all(r_xy_ls[r]));
        auto events = gen_event(r);
        for (auto &e: events) {
            if (e.type == Insert) {
                tr.add(li_y.get_i(e.y1), 1);
            } else if (e.type == Left) {
                Ans[e.id] -= tr.query(li_y.get_i(e.y1), li_y.get_i(e.y2));
                Ans[e.id] -= redundant_circle_cnt(r,e.x+r,e.y1+r,-1,-1);
                Ans[e.id] -= redundant_circle_cnt(r,e.x+r,e.y2-r,-1,1);
            } else {
                Ans[e.id] += tr.query(li_y.get_i(e.y1), li_y.get_i(e.y2));
                Ans[e.id] -= redundant_circle_cnt(r,e.x-r,e.y1+r,1,-1);
                Ans[e.id] -= redundant_circle_cnt(r,e.x-r,e.y2-r,1,1);
            }
        }
    }
		
		// 查找以这个 x 为首的，在范围 [ly,ry] 之间的这个点的数量
    ll query_r_x_l_r_cnt(ll r, ll x, ll ly, ll ry) {
        if (ly > ry) {
            return 0;
        }
        auto &xy_ls = r_xy_ls[r];
        auto itl = lower_bound(all(xy_ls), X_y{x, ly});

        if (itl == xy_ls.end()) {
            return 0;
        }
        if (itl->x != x) {
            return 0;
        }
        if (itl->y > ry) {
            return 0;
        }
        auto itr = upper_bound(all(xy_ls), X_y{x, ry});
        ll num = itr - itl;
        return num;
    }
		
		// 计算边缘的，可能被多算的这个点。
    ll redundant_circle_cnt(ll r, ll x, ll y, ll dirx, ll diry) {
        ll res = 0;
        for (int dx = 1; dx <= r; ++dx) {
            ll tox = x + dirx * dx;
            ll disy = sqrtl(r * r - dx * dx);
            ll toy = y + diry * disy;
            ll ly = min(toy + diry, y + diry * r);
            ll ry=max(toy + diry, y + diry * r);
            res += query_r_x_l_r_cnt(r, tox, ly, ry);
        }
        return res;
    }

    Solve() : r_xy_ls(32) {
        cin >> N >> M;
        li_y.reserve(N + M);
        // for (int i = 1; i <= 30; ++i) r_xy_ls[i].reserve(N);
        for (int i = 1; i <= N; ++i) {
            ll x, y, d;
            cin >> x >> y >> d;
            r_xy_ls[d].push_back({x, y});
            li_y.add(y);
        }
        events_backup.reserve(N + 30 * M);
        Ans.resize(M);
        for (int i = 0; i < M; ++i) {
            ll x1, y1, x2, y2;
            cin >> x1 >> y1 >> x2 >> y2;
            for (int r = 0; r <= 30; ++r) {
                li_y.add(y1 - r, y2 + r);
            }
            events_backup.push_back({x1, y1, Left, i, y2});
            events_backup.push_back({x2, y1, Right, i, y2});
        }
        sort(all(events_backup));
        li_y.init();
        for (int i = 1; i <= 30; ++i) {
            solve_single_r(i);
        }
        for (int i = 0; i < M; ++i) {
            cout << Ans[i] << "\n";
        }
    }
};

AC代码

AC
https://acm.hdu.edu.cn/contest/view-code?cid=1198&rid=19570

源代码

// teamname: Gospel_rock
/**
 * Problem: 守矢晨风
 * Contest: 
 * Judge: HDOJ
 * URL: https://acm.hdu.edu.cn/contest/problem?cid=1198&pid=1005
 * Created: 2026-04-02 10:51:46
 * 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 debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

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;
const double PI = acos(-1.0);

ll lT, testcase;

/*
 *
 */

/* 参考了 https://github.com/hh2048/XCPC/blob/484e9e0e6e4f127f187eb3df5bc419e9ec863795/02%20-%20%E6%89%93%E5%8D%B0%E7%A8%BF%E6%A8%A1%E6%9D%BF%E6%B1%87%E6%80%BB/08%20-%20%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84.md#L737
 *
 */
template<typename T>
struct Compress_ {
    // shift=0 就是采用 0-based 下标
    // shift=1 就是采用 1-based 下标
    int n, shift = 1;
    vector<T> alls;

    Compress_() {
    }

    // 预估大小
    Compress_(ll n_) {
        alls.reserve(n_);
    }

    Compress_(vector<T> in) : alls(in) {
        init();
    }

    void add(T x) {
        alls.emplace_back(x);
    }

    template<typename... Args>
    void add(T x, Args... args) {
        add(x), add(args...);
    }

    void reserve(ll n_) {
        alls.reserve(n_);
    }

    void init() {
        alls.emplace_back(numeric_limits<T>::max());
        sort(alls.begin(), alls.end());
        alls.resize(unique(alls.begin(), alls.end()) - alls.begin());
        this->n = alls.size();
    }

    int size() {
        return n;
    }

    int get_i(T x) {
        // 返回 x 元素的新下标
        return upper_bound(alls.begin(), alls.end(), x) - alls.begin() + shift;
    }

    T operator[](int idx) {
        // 根据新下标返回原来元素
        assert(idx - shift < n);
        return idx - shift < n ? alls[idx - shift] : -1;
    }

    bool contains(T x) {
        // 查找元素 x 是否存在
        return binary_search(alls.begin(), alls.end(), x);
    }

    friend auto &operator<<(ostream &o, const auto &j) {
        cout << "{";
        for (auto it: j.alls) {
            o << it << " ";
        }
        return o << "}";
    }
};

// by znzryb
// 普通的单点修改区间查询树状数组，含有查找第K个空位，第K个元素的功能
// https://www.codechef.com/viewsolution/1179893708 查找第K个元素测试
// 第K个空位的测试应该是一道abc的题目，但是当时没保存
struct BIT {
    vector<ll> tr;
    int n;

    inline int lowbit(int x) {
        return x & (-x);
    }

    BIT(int ln) {
        // 构造+初始化函数
        n = ln;
        tr.resize(n + 5, 0);
    }

    BIT() {
    }

    inline void add(int p, ll x) {
        if (p == 0) return;
        while (p <= n) {
            tr[p] += x;
            p += lowbit(p);
        }
    }

    inline ll query(int l, int r) {
        ll lres = 0, rres = 0;
        l -= 1;
        while (l > 0) {
            lres += tr[l];
            l -= lowbit(l);
        }
        while (r > 0) {
            rres += tr[r];
            r -= lowbit(r);
        }
        return rres - lres;
    }

    inline int findkth(int k) {
        // 找到第k个元素，当然应当是要求只能出现0和1
        int x = 0, sum = 0;
        for (int i = __lg(n); ~i; --i) {
            x += 1 << i;
            if (x >= n || sum + tr[x] >= k) {
                x -= 1 << i;
            } else {
                sum += tr[x];
            }
        }
        return x + 1; // 我们始终让cx < k，所以返回的就是最大的比k小的，+1就是新元素出现的地方
    }

    inline int kthspace(int k) {
        // 找到第k个空位，当然应当是要求只能出现0和1
        int cx = 0;
        for (int i = 1 << 20; i > 0; i >>= 1) {
            // 这个你可以理解为不断缩小步长的搜索
            if (cx + i <= n && lowbit(cx + i) - tr[cx + i] < k) {
                // lowbit(cx)-tr[cx+i] 表示cx+i这个树状数组区间有多少空位
                k -= lowbit(cx + i) - tr[cx + i];
                cx += i;
            }
        }
        return cx + 1; // 我们始终让cx < k，所以返回的就是最大的比k小的，+1就是新空位出现的地方
    }
};

struct X_y {
    ll x;
    ll y;

    bool operator<(const X_y &o) const {
        if (x != o.x) return x < o.x;
        return y < o.y;
    }

    bool operator==(const X_y &o) const {
        return x == o.x && y == o.y;
    }
};

enum my_enum {
    Left,
    Insert,
    Right,
};

struct Event {
    ll x, y1;
    my_enum type;
    int id;
    ll y2;

    bool operator<(const Event &o) const {
        if (x != o.x) return x < o.x;
        if (type != o.type) return type < o.type;
        return y1 < o.y1;
    }
};

struct Solve {
    ll N, M;
    Compress_<ll> li_y;
    vector<vector<X_y> > r_xy_ls;
    vector<Event> events_backup;
    vector<int> Ans;

    vector<Event> gen_event(ll r) {
        // vector<Event> tmp_events;
        vector<Event> events;
        // tmp_events.reserve(SZ(r_xy_ls[r]));
        for (auto [x,y]: r_xy_ls[r]) {
            events.push_back({x, y, Insert});
        }
        for (auto e: events_backup) {
            e.y1 -= r;
            e.y2 += r;
            if (e.type == Left) {
                e.x -= r;
            } else if (e.type == Right) {
                e.x += r;
            }
            events.push_back(e);
        }
        sort(all(events));
        return events;
    }

    // 这边的这个计算是不管这个边缘的，可能被多算的点的
    void solve_single_r(ll r) {
        BIT tr(li_y.size());
        sort(all(r_xy_ls[r]));
        auto events = gen_event(r);
        for (auto &e: events) {
            if (e.type == Insert) {
                tr.add(li_y.get_i(e.y1), 1);
            } else if (e.type == Left) {
                Ans[e.id] -= tr.query(li_y.get_i(e.y1), li_y.get_i(e.y2));
                Ans[e.id] -= redundant_circle_cnt(r,e.x+r,e.y1+r,-1,-1);
                Ans[e.id] -= redundant_circle_cnt(r,e.x+r,e.y2-r,-1,1);
            } else {
                Ans[e.id] += tr.query(li_y.get_i(e.y1), li_y.get_i(e.y2));
                Ans[e.id] -= redundant_circle_cnt(r,e.x-r,e.y1+r,1,-1);
                Ans[e.id] -= redundant_circle_cnt(r,e.x-r,e.y2-r,1,1);
            }
        }
    }

    ll query_r_x_l_r_cnt(ll r, ll x, ll ly, ll ry) {
        if (ly > ry) {
            return 0;
        }
        auto &xy_ls = r_xy_ls[r];
        auto itl = lower_bound(all(xy_ls), X_y{x, ly});

        if (itl == xy_ls.end()) {
            return 0;
        }
        if (itl->x != x) {
            return 0;
        }
        if (itl->y > ry) {
            return 0;
        }
        auto itr = upper_bound(all(xy_ls), X_y{x, ry});
        ll num = itr - itl;
        return num;
    }

    ll redundant_circle_cnt(ll r, ll x, ll y, ll dirx, ll diry) {
        ll res = 0;
        for (int dx = 1; dx <= r; ++dx) {
            ll tox = x + dirx * dx;
            ll disy = sqrtl(r * r - dx * dx);
            ll toy = y + diry * disy;
            ll ly = min(toy + diry, y + diry * r);
            ll ry=max(toy + diry, y + diry * r);
            res += query_r_x_l_r_cnt(r, tox, ly, ry);
        }
        return res;
    }

    Solve() : r_xy_ls(32) {
        cin >> N >> M;
        li_y.reserve(N + M);
        // for (int i = 1; i <= 30; ++i) r_xy_ls[i].reserve(N);
        for (int i = 1; i <= N; ++i) {
            ll x, y, d;
            cin >> x >> y >> d;
            r_xy_ls[d].push_back({x, y});
            li_y.add(y);
        }
        events_backup.reserve(N + 30 * M);
        Ans.resize(M);
        for (int i = 0; i < M; ++i) {
            ll x1, y1, x2, y2;
            cin >> x1 >> y1 >> x2 >> y2;
            for (int r = 0; r <= 30; ++r) {
                li_y.add(y1 - r, y2 + r);
            }
            events_backup.push_back({x1, y1, Left, i, y2});
            events_backup.push_back({x2, y1, Right, i, y2});
        }
        sort(all(events_backup));
        li_y.init();
        for (int i = 1; i <= 30; ++i) {
            solve_single_r(i);
        }
        for (int i = 0; i < M; ++i) {
            cout << Ans[i] << "\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 solve;
    return 0;
}

/*
AC
https://acm.hdu.edu.cn/contest/view-code?cid=1198&rid=19570

*/

心路历程（WA，TLE，MLE……）

也是成功一次 AC 了，当然，在写一些模块的时候，ai 也帮助我进行了一些东西。

The 2025 Jiangsu Collegiate Programming Contest（2025 江苏省赛）——H. Loose Subsequences（求本质不同子序列的方法）

Posted on 2026-03-30 Edited on 2026-04-06

题目大意

题目描述
给定一个长度为 $n$ 、仅由小写字母组成的字符串 $S$ 以及一个非负整数 $k$ 。
需要计算 $S$ 的本质不同的非空 $k$ -松散子序列的数量，并将结果对 $998244353$ 取模。

相关定义

$k$ -松散子序列：如果子序列 $T$ 在原字符串 $S$ 中对应的下标序列为 $pos_1, pos_2, \dots, pos_m$ ，且满足对于所有的 $i \in [1, m-1]$ ，都有 $pos_{i+1} - pos_i > k$ ，那么 $T$ 就是一个 $k$ -松散子序列。即子序列中原串相邻提取字符的原始位置距离必须严格大于 $k$ 。
本质不同：两个子序列被认为是不同的，当且仅当它们的长度不同，或者它们在某个对应位置上的字符不相同（即只对比提取出的字符构成的字符串本身是否一致）。

输入格式
第一行包含一个整数 $T$ （ $1 \le T \le 10^6$ ），表示测试用例数。
对于每组测试用例：
第一行包含两个整数 $n, k$ （ $1 \le n \le 10^6, 0 \le k \le n$ ）。
第二行包含一个长度为 $n$ 的字符串 $S$ ，保证仅包含小写字母。
保证所有测试用例的 $\sum n \le 10^6$ 。

输出格式
对于每组测试用例，输出一行一个整数，表示本质不同的非空 $k$ -松散子序列的数量对 $998244353$ 取模的结果。

样例

输入:
3
4 1
aabb
5 2
abcab
7 3
abcdece

输出:
3
6
10

样例解释

对于第一个测试用例（ $S = \text{aabb}$ ， $k = 1$ ），下标位置差必须严格大于 $1$ 。满足条件的本质不同的子序列有 a、b、ab。
对于第二个测试用例（ $S = \text{abcab}$ ， $k = 2$ ），下标位置差必须严格大于 $2$ 。满足条件的本质不同的子序列有 a、b、c、aa、ab、bb。

思路讲解

gemini 的这个思路

题目描述

给定一个长度为 $n$ 、仅由小写字母组成的字符串 $S$ 以及一个非负整数 $k$ 。
需要计算 $S$ 的本质不同的非空 $k$ -松散子序列的数量，并将结果对 $998244353$ 取模。

$k$ -松散子序列：如果子序列在原字符串 $S$ 中对应的下标序列为 $pos_1, pos_2, \dots, pos_m$ ，且满足对于所有的 $i \in [1, m-1]$ ，都有 $pos_{i+1} - pos_i > k$ ，则该子序列为 $k$ -松散子序列。即相邻选择的字符在原串中的距离必须严格大于 $k$ 。
本质不同：两个子序列被认为是不同的，当且仅当它们作为字符串本身不一致，或者长度不同。

算法思路

本题可以使用动态规划来解决。
为了避免重复计算本质相同的子序列，我们可以采用贪心匹配的思想：对于任何一个合法的子序列，为了给后续字符留下最大的选择空间，我们总是贪心地在原串中寻找它的第一个可用匹配位置。在这个约束下，每个合法的 $k$ -松散子序列都唯一对应原串中的一种提取方式。
我们定义 $V_x$ 为：在后缀 $S_{x \dots n}$ 中，能够选出的本质不同的合法序列数量（第一步选择没有 $+k$ 的位置限制，但后续的选择仍需满足距离 $>k$ 的限制）。
考虑如何从 $V_{x+1}$ 转移到 $V_x$ ：
与后缀 $S_{x+1 \dots n}$ 相比，后缀 $S_{x \dots n}$ 多了一个字符 $S_x$ 可以作为序列的开头。

如果我们将 $S_x$ 作为子序列的第一个字符，那么下一个字符必须从下标 $\ge x+k+1$ 的位置开始选择。这种情况能产生的合法子序列数量为 $1 + V_{x+k+1}$ （其中 $1$ 代表仅由 $S_x$ 构成的长度为 $1$ 的子序列）。
然而，在 $V_{x+1}$ 的结果中，可能已经包含了以 $S_x$ 这个字符开头的序列——它们是把 $S_x$ 的下一次出现位置（记为 $nxt_x$ ）作为起点的。为了防止重复计算以该字符开头的序列，我们需要把这部分重复的序列减去。以 $nxt_x$ 作为起点能产生的子序列数量为 $1 + V_{nxt_x+k+1}$ 。
综上所述，我们可以得出状态转移方程。
定义辅助数组 $W_x$ 表示选择位置 $x$ 作为开头时的组合数：
如果 $x \le n$ ，则 $W_x \leftarrow 1 + V_{x+k+1}$ ；否则 $W_x \leftarrow 0$ 。
那么状态转移方程为：
$V_x \leftarrow (V_{x+1} + W_x - W_{nxt_x} \pmod{998244353} + 998244353) \bmod 998244353$
我们只需从右向左（ $x$ 从 $n$ 递减到 $1$ ）遍历字符串计算 $V_x$ ，最终的答案即为 $V_1$ 。

代码实现

#include <iostream>
#include <vector>
#include <string>

using namespace std;

const int MOD = 998244353;

void solve() {
    int n, k;
    if (!(cin >> n >> k)) return;
    string s;
    cin >> s;

    // nxt[i] 记录字符 s[i-1] 在位置 i 之后第一次出现的下标（1-indexed）
    vector<int> nxt(n + 1, n + 1);
    vector<int> last_seen(26, n + 1);

    for (int i = n; i >= 1; --i) {
        int c = s[i - 1] - 'a';
        nxt[i] = last_seen[c];
        last_seen[c] = i;
    }

    // V[i] 记录在后缀 s[i...n] 中本质不同的合法子序列数量
    // 数组大小开到 n + k + 5 以防止越界访问
    vector<int> V(n + k + 5, 0);

    for (int i = n; i >= 1; --i) {
        // 如果选择当前的字符，后续的合法序列数量加上它本身（1）
        int w_i = V[i + k + 1] + 1;
        if (w_i == MOD) w_i = 0;

        // 如果该字符在之后还出现过，需要减去在下一次出现位置处选择该字符所产生的情况
        int w_nxt = 0;
        if (nxt[i] <= n) {
            w_nxt = V[nxt[i] + k + 1] + 1;
            if (w_nxt == MOD) w_nxt = 0;
        }

        // 状态转移：V[i] = V[i + 1] + w_i - w_nxt
        int v = V[i + 1] + w_i;
        if (v >= MOD) v -= MOD;
        v -= w_nxt;
        if (v < 0) v += MOD;

        V[i] = v;
    }

    cout << V[1] << "\\n";
}

int main() {
    // 优化输入输出流速度
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    if (cin >> t) {
        while (t--) {
            solve();
        }
    }
    return 0;
}

复杂度分析与边界情况

算法说明：
我们利用了子序列自动机的贪心匹配性质，将“本质不同”的限制转换为“每次必须选取该字符第一次出现的位置”。接着使用动态规划，通过类似于经典本质不同子序列计数（即 $k=0$ 时）的加减容斥思想，巧妙避开了状态中带有位置距离限制的遍历，将每一次状态转移做到了 $O(1)$ 的极致效率。
时间复杂度：

预处理 nxt 数组需要逆序遍历一次字符串，花费 $O(n)$ 的时间。
动态规划过程只需要从后向前遍历一次，每次循环内部都是简单的条件判断和常数级别的加减运算，花费 $O(n)$ 的时间。
因此对于每组测试用例，时间复杂度为 $O(n)$ 。所有测试用例的总时间复杂度为 $O(\sum n)$ ，最大计算量约 $10^6$ 次操作，可以在 $1$ 秒的时间限制内极其轻松地通过。
空间复杂度：
我们创建了长度为 $n+1$ 的 nxt 数组，以及长度为 $n+k+5$ 的动态规划数组 V。两个数组的大小均为 $O(n)$ 级别。
由于每次都是动态分配，空间复杂度为 $O(n)$ 。最大极限情况下占用内存不足 $15\text{MB}$ ，严格符合并远低于 $512\text{MB}$ 的内存限制要求。
边界情况处理：
$k \ge n$ ：此时任何选取的字符下标加上 $k+1$ 都会超出字符串长度，即 $V_{i+k+1}$ 必然为 $0$ 。此时原串中每种出现过的字符只会被单独算作一个长度为 $1$ 的子序列（由于 $W_{nxt_x}$ 的减法抵消作用，每个不同的字母只会全局计算一次）。代码中分配的空间 n + k + 5 完美覆盖了这一情况，不仅逻辑正确也不会出现数组越界。
取模运算的负数情况：由于状态转移中含有减法（容斥），直接取模可能会导致负数结果传递。代码中采用了加减法与判断结合的方式（v -= w_nxt; if (v < 0) v += MOD;）手动修正负数。这种方式不仅避免了除法取模运算符 % 带来的指令周期损耗，还确保了最终状态值绝对正确且总是正整数。

呃，这个我们需要想办法做到求本质不同的这个所有子序列。

我们转移的时候，就是应该以 s[i] 开头的串，在我们所有的这个的计数之中，应该以 s[i] 开头的串只应该真的以 i 开头的时候被计算，因此后面的应该被减去。（当然，我们是从后往前遍历）

具体而言，这个转移式子是：

next[i] 存在:\ dp[i]\gets 2\times dp[i+1]-(dp[next[i]+1]+1)+1 \\ dp[i]\gets 2\times dp[i+1]-dp[next[i]+1] \\ next[i] 不存在:\ dp[i]\gets 2\times dp[i+1]+1

注意，为什么是减去 $dp[next[i]+1]+1$ 呢？因为其实这个才是含有 $next[i]$ 的子序列的所有数量。

当然，这个是求本质不同的这个子序列的时候，我们要计算 k-松散子序列。

计算 k-松散子序列：

next[i] 不存在:\ dp[i]\gets 2\times dp[i+k+1]+1 \\ next[i] 存在:\ dp[i]\gets 2\times dp[i+k+1]+1-(dp[next[i]+k+1]+1) \\ dp[i]\gets 2\times dp[i+k+1]-dp[next[i]+k+1]

AC代码

源代码

心路历程（WA，TLE，MLE……）

如何开大栈空间

Posted on 2026-03-29 Edited on 2026-04-06

杭电 OJ 暂不支持调整栈空间大小。如果使用 G++ 提交代码，并且代码中含有递归，递归层数较深，会返回 Runtime Error (STACK_OVERFLOW)。添加如下代码可以开大栈空间：

int main() {
    int size(256<<20);  // 256M
    __asm__ ( "movq %0, %%rsp\n"::"r"((char*)malloc(size)+size));
    // 关同步流代码
    // 主程序代码
    exit(0); // 一定要添加这一条，不然会返回 Runtime Error (ACCESS_VIOLATION)
}

2026 杭电春季联赛 2——1002-庭扫落樱（二分图最大匹配）（最小边覆盖和最大匹配之间的关系）

Posted on 2026-03-29 Edited on 2026-04-06

题目大意

题目描述

给定二维平面第一象限上的 $n$ 个弹幕发射器。第 $i$ 个发射器位于坐标 $(x_i, y_i)$ ，并向四个方向之一发射一条射线（激光）：

$d_i = 0$ ：向上发射
$d_i = 1$ ：向右发射
$d_i = 2$ ：向下发射
$d_i = 3$ ：向左发射

射线的照明路径包含发射器本身所在的位置。题目保证任意两个发射器不会同时在对方的照明路径上。

现在可以在平面上放置障碍物（允许放置在发射器所在的坐标上），只要障碍物位于某条射线上，就能阻挡该射线的照射。求最少需要放置多少个障碍物，才能使得所有 $n$ 个发射器的照射路径上都至少包含一个障碍物。

输入格式

第一行包含一个整数 $t$ （ $1 \le t \le 100$ ），表示测试用例的数量。

每个测试用例第一行包含一个整数 $n$ （ $1 \le n \le 300$ ），表示发射器的数量。
接下来 $n$ 行，每行包含三个整数 $x_i, y_i, d_i$ （ $1 \le x_i, y_i \le 10^9$ ， $d_i \in \{0, 1, 2, 3\}$ ），表示发射器的坐标与发射方向。

保证所有测试用例中 $n$ 的总和不超过 $3000$ 。

输出格式

对于每个测试用例，输出一行一个整数，表示最少需要放置的障碍物数量。

样例输入

样例输出

1
2

3
1

样例解释

在第一个测试用例中，有 $6$ 个发射器。一种最优方案是放置 $3$ 个障碍物，具体位置如下：

在坐标 $(5, 7)$ 处放置一个障碍物：该点覆盖了第 $1$ 束（从 $(5,5)$ 向上）、第 $2$ 束（从 $(3,7)$ 向右）以及第 $5$ 束（从 $(5,2)$ 向上）激光。
在坐标 $(9, 1)$ 处放置一个障碍物：该点覆盖了第 $3$ 束（从 $(9,9)$ 向下）以及第 $4$ 束（从 $(9,1)$ 向左）激光。
在坐标 $(-2025, 20)$ 处放置一个障碍物：该点覆盖了第 $6$ 束（从 $(1,20)$ 向左）激光。

该方案共使用了 $3$ 个障碍物，且可以证明不存在比 $3$ 更少的放置方案。

思路讲解

一种错误的图论建模方式是把激光当作左边的点，把这个障碍物当成右边的点，但是这样子建图是做不出来这道题目的，因为我们不是要让激光和障碍物一一匹配，这个非常容易就能做到。

P3386 【模板】二分图最大匹配

那么要做这道题目，最重要的就是我们要把障碍物看成连边，左边的点指的是这个方向为上下的点，右边的点指的是这个方向为左右的点。

void Solve() {
    ll N;
    cin >> N;
    vector<X_y_d> xyd_ls(N);
    for (int i = 0; i < N; ++i) {
        cin >> xyd_ls[i].x >> xyd_ls[i].y >> xyd_ls[i].d;
    }
    xyd_ls = unique_xyd_ls(xyd_ls);
    auto g = build_graph(xyd_ls);
    Bi_graph_matcher matcher(g,SZ(xyd_ls));
    ll mx_match = matcher.mx_match();
    ll ans = (SZ(xyd_ls) - 2 * mx_match) + mx_match;
    cout << ans << "\n";
}

AC代码

AC
https://acm.hdu.edu.cn/contest/view-code?cid=1198&rid=18859

源代码

// teamname: Gospel_rock
/**
 * Problem: 庭扫落樱
 * Contest: 
 * Judge: HDOJ
 * URL: https://acm.hdu.edu.cn/contest/problem?cid=1198&pid=1002
 * Created: 2026-03-29 18:54:03
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>

#include <utility>
#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 debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

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;
const double PI = acos(-1.0);

ll lT, testcase;

/*
 *
 */
struct X_y_d {
    ll x;
    ll y;
    ll d;
};

struct X_y {
    ll x;
    ll y;

    bool operator<(const X_y &o) const {
        if (x != o.x) return x < o.x;
        return y < o.y;
    }
};

bool is_two_laser_intersect(X_y_d a, X_y_d b) {
    if ((a.d==0 || a.d==2) && (b.d==1 || b.d==3)) {
        X_y node = {a.x, b.y};
        if (a.d == 0) {
            if (node.y < a.y) {
                return false;
            }
        }
        if (a.d == 2) {
            if (node.y > a.y) {
                return false;
            }
        }
        if (b.d == 1) {
            if (node.x < b.x) {
                return false;
            }
        }
        if (b.d == 3) {
            if (node.x > b.x) {
                return false;
            }
        }
        return true;
    }else {
        return false;
    }
}

auto unique_xyd_ls_detail(const vector<X_y_d> &xyd_ls, ll offset) {
    vector<X_y_d> res;
    res.reserve(SZ(xyd_ls));
    map<ll, ll> mp1, mp3;
    for (auto [x,y,d]: xyd_ls) {
        if (offset) {
            swap(x, y);
        }
        if (d == 0 + offset) {
            if (!mp1.contains(x)) {
                mp1[x] = y;
            } else {
                mp1[x] = max(mp1[x], y);
            }
        } else if (d == 2 + offset) {
            if (!mp3.contains(x)) {
                mp3[x] = y;
            } else {
                mp3[x] = min(mp3[x], y);
            }
        }
    }
    for (auto [x_,y_]: mp1) {
        auto [x,y] = make_tuple(x_, y_);
        if (offset) swap(x, y);
        res.push_back({x, y, 0 + offset});
    }
    for (auto [x_,y_]: mp3) {
        auto [x,y] = make_tuple(x_, y_);
        if (offset) swap(x, y);
        res.push_back({x, y, 2 + offset});
    }
    return res;
}

auto unique_xyd_ls(const vector<X_y_d> &xyd_ls) {
    auto res1 = unique_xyd_ls_detail(xyd_ls, 0);
    auto res2 = unique_xyd_ls_detail(xyd_ls, 1);
    res1.insert(res1.end(), res2.begin(), res2.end());
#ifdef LOCAL
    cerr << "xyd_ls:\n";
    for (int i = 0; i < SZ(xyd_ls); ++i) {
        cerr << xyd_ls[i].x << " " << xyd_ls[i].y << " " << xyd_ls[i].d << "\n";
    }
#endif
    return res1;
}


// 注意，二分图构建的是有向图
auto build_graph(const vector<X_y_d> &xyd_ls) {
    ll idx = SZ(xyd_ls);
    map<X_y, ll> mp;
    vector<vector<ll> > g(SZ(xyd_ls) + 2);
    for (int i = 0; i < SZ(xyd_ls); ++i) {
        for (int j = i + 1; j < SZ(xyd_ls); ++j) {
            if (xyd_ls[i].d == 0 || xyd_ls[i].d == 2) {
                auto flag = is_two_laser_intersect(xyd_ls[i], xyd_ls[j]);
                if (!flag) {
                    continue;
                }
                g[i].push_back(j);
            }
        }
    }
    // #ifdef LOCAL
    //     debug2d(g);
    // #endif
    return g;
}

struct Bi_graph_matcher {
    vector<vector<ll> > g;
    vector<char> vis;
    vector<ll> match;
    ll left_cnt;

    Bi_graph_matcher(vector<vector<ll> > _g, ll _left_cnt) : g(std::move(_g)), vis(SZ(g) + 2), match(SZ(g) + 2, -1),
                                                             left_cnt(_left_cnt) {
    }

    bool find(ll u) {
        for (auto to: g[u]) {
            if (vis[to]) {
                continue;
            }
            vis[to] = true;
            // 如果 v 还没有匹配，或者 v 原本匹配的人能找到新的匹配（腾出位置）
            if (match[to] == -1 || find(match[to])) {
                match[to] = u;
                return true;
            }
        }
        return false;
    }

    ll mx_match() {
        ll ans = 0;
        for (int i = 0; i <= left_cnt; ++i) {
            vis.assign(SZ(g) + 2, 0);
            if (find(i)) {
                ++ans;
            }
        }
        return ans;
    }
};


void Solve() {
    ll N;
    cin >> N;
    vector<X_y_d> xyd_ls(N);
    for (int i = 0; i < N; ++i) {
        cin >> xyd_ls[i].x >> xyd_ls[i].y >> xyd_ls[i].d;
    }
    xyd_ls = unique_xyd_ls(xyd_ls);
    auto g = build_graph(xyd_ls);
    Bi_graph_matcher matcher(g,SZ(xyd_ls));
    ll mx_match = matcher.mx_match();
    ll ans = (SZ(xyd_ls) - 2 * mx_match) + mx_match;
    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
    // auto start = std::chrono::high_resolution_clock::now();
#endif
    cin >> lT;
    for (testcase = 1; testcase <= lT; ++testcase)
        Solve();

    return 0;
}

/*
AC
https://acm.hdu.edu.cn/contest/view-code?cid=1198&rid=18859


pair<bool, X_y> intersect_two_laser(X_y_d a, X_y_d b) {
    // pair<bool,  > res;
    if (a.d == b.d) return {false, {}};
    if (a.d == 0 && b.d == 2) return {false, {}};
    if (a.d == 1 && b.d == 3) return {false, {}};
    if ((a.d==0 && b.d==1)) {

    }
    X_y node = {a.x, b.y};
    if (a.d == 0) {
        if (node.y < a.y) {
            return {false, {}};
        }
    }
    if (a.d == 2) {
        if (node.y > a.y) {
            return {false, {}};
        }
    }
    if (a.d == 1) {
        if (node.x < a.x) {
            return {false, {}};
        }
    }
    if (a.d == 3) {
        if (node.x > a.x) {
            return {false, {}};
        }
    }
    return {true, node};
}

// 注意，二分图构建的是有向图
auto build_graph(const vector<X_y_d> &xyd_ls) {
    ll idx = SZ(xyd_ls);
    map<X_y, ll> mp;
    vector<vector<ll> > g(SZ(xyd_ls) + 2);
    g.reserve(4 * SZ(xyd_ls));
    for (int i = 0; i < SZ(xyd_ls); ++i) {
        X_y xy = {xyd_ls[i].x, xyd_ls[i].y};
        ll node;
        if (mp.contains(xy)) {
            node = mp[xy];
        } else {
            ++idx;
            g.push_back({});
            node = idx;
            mp[xy] = idx;
        }
        g[i].push_back(node);
        // g[node].push_back(i);
    }
    for (int i = 0; i < SZ(xyd_ls); ++i) {
        for (int j = i + 1; j < SZ(xyd_ls); ++j) {
            auto [flag,xy] = intersect_two_laser(xyd_ls[i], xyd_ls[j]);
            if (!flag) {
                continue;
            }
            ll node;
            if (mp.contains(xy)) {
                node = mp[xy];
            } else {
                ++idx;
                g.push_back({});
                node = idx;
                mp[xy] = idx;
            }
            g[i].push_back(node);
            g[j].push_back(node);
            // g[node].push_back(i);
            // g[node].push_back(j);
        }
    }
#ifdef LOCAL
    debug2d(g);
#endif
    return g;
}
*/

心路历程（WA，TLE，MLE……）

最好显式忽略这个其他情况：

使用 offset 进行 swap，最后也要 swap 回来。

将哨兵值设置为 -1，可以避免 0-based 造成问题。

Nebius Round 2 (Codeforces Round 1088, Div. 1 + Div. 2)——CF-2211-B. Mickey Mouse Constructive

Posted on 2026-03-29 Edited on 2026-04-06

题目大意

题目描述

给定一个数组 $a$ ，定义 $f(a)$ 为将 $a$ 划分成一个或多个连续子数组的方案数，需满足以下条件：

每个元素恰好属于一个子数组。
所有子数组的元素和都相等。

例如，对于 $a=[1,1]$ ， $f(a)=2$ ，因为有两种合法的划分方案：

$[1,1]$ ，此时唯一的子数组和为 $2$ 。
$[1]+[1]$ ，此时两个子数组和均为 $1$ 。

给定两个整数 $x$ 和 $y$ 。你需要构造一个长度为 $x+y$ 的数组 $a$ ，其中包含 $x$ 个 $1$ 和 $y$ 个 $-1$ 。
你需要求出在所有合法的数组 $a$ 中， $f(a)$ 的最小值，并将该最小值对 $676767677$ 取模后输出。同时，你需要输出一个能达到该最小值的数组构造方案。

注意：你需要最小化的是 $f(a)$ 本身，然后将这个最小值对 $676767677$ 取模，而不是去最小化 $f(a) \bmod 676767677$ 的结果。

输入格式

第一行包含一个整数 $t$ ( $1 \le t \le 10^4$ )，表示测试用例的数量。

接下来每个测试用例包含一行，包含两个整数 $x$ 和 $y$ ( $0 \le x, y \le 2 \cdot 10^5$ )，保证 $x+y \ge 1$ 。

保证所有测试用例中 $x$ 的总和与 $y$ 的总和均不超过 $2 \cdot 10^5$ 。

输出格式

对于每个测试用例，输出两行：
第一行输出 $f(a)$ 的最小值对 $676767677$ 取模的结果。
第二行输出一个达到该最小值的数组 $a$ 的元素（用空格分隔）。

样例输入

样例输出

2
1 1
1
1 -1
1
-1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1
2
-1 -1 -1 1

样例解释

在第一个测试用例中， $x=2$ 且 $y=0$ 。唯一可能的数组是 $a=[1,1]$ ，正如题目描述中所解释的，此时 $f(a)=2$ 。

在第二个测试用例中， $x=1$ 且 $y=1$ 。一个能使 $f(a)$ 最小化的合法数组是 $a=[1,-1]$ 。此时 $f(a)=1$ ，因为唯一能使所有子数组和相等的划分方式就是不进行任何分割（即 $[[1,-1]]$ ，子数组和为 $0$ ）。

思路讲解

void Solve() {
    ll X, Y;
    cin >> X >> Y;
    vector<ll> A(X + Y + 2);
    for (int i = 1; i <= X; ++i) {
        // cout << 1 << " ";
        A[i] = 1;
    }
    for (int i = 1; i <= Y; ++i) {
        // cout << -1 << " ";
        A[i + X] = -1;
    }
    ll s = llabs(X - Y);
    ll ans = 1;
    // 这里要采用求约数个数的方法
    if (s != 0) {
        ans = 0;
        for (ll d = 1; d * d <= s; ++d) {
            if (s % d == 0) {
                ++ans;
                if (d * d != s) ++ans;
            }
        }
    }
    cout << ans << "\n";
    for (int i = 1; i <= X + Y; ++i) {
        cout << A[i] << " ";
    }
    cout << "\n";
    // mod
}

AC代码

https://codeforces.com/contest/2211/submission/368623804

源代码

// teamname: Gospel_rock
/**
 * Problem: B. Mickey Mouse Constructive
 * Contest: Nebius Round 2 (Codeforces Round 1088, Div. 1 + Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2211/problem/B
 * Created: 2026-03-28 22:48:14
 * 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 debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

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 = 676767677;
static constexpr double eps = 1e-8;
const double PI = acos(-1.0);

ll lT, testcase;

/*
 *
 */

void Solve() {
    ll X, Y;
    cin >> X >> Y;
    vector<ll> A(X + Y + 2);
    for (int i = 1; i <= X; ++i) {
        // cout << 1 << " ";
        A[i] = 1;
    }
    for (int i = 1; i <= Y; ++i) {
        // cout << -1 << " ";
        A[i + X] = -1;
    }
//     ll N = X + Y;
//     ll sum = X - Y;
//     ll cur = 0;
//     ll ans = 0;
//     for (int i = 1; i <= N; ++i) {
//         cur += A[i];
//         ll rem = sum - cur;
// #ifdef LOCAL
//         debug(cur);
//         debug(rem);
//         cend;
// #endif
//         if (cur == 0) {
//             // assert(0);
//             if (cur == rem) {
//                 ++ans;
//                 ans %= mod;
//             }
//             continue;
//         }
//         if ((rem * cur) >= 0 && rem % cur == 0) {
//             ++ans;
//             ans %= mod;
//         }
//     }
    ll s = llabs(X - Y);
    ll ans = 1;
    if (s != 0) {
        ans = 0;
        for (ll d = 1; d * d <= s; ++d) {
            if (s % d == 0) {
                ++ans;
                if (d * d != s) ++ans;
            }
        }
    }
    cout << ans << "\n";
    for (int i = 1; i <= X + Y; ++i) {
        cout << A[i] << " ";
    }
    cout << "\n";
    // mod
}

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;
}

/*



// if (Y != 0) {
    //     ll N = X + Y;
    //     ll sum = X;
    //     ll ans = 1;
    //     for (ll i = 1; i <= Y; ++i) {
    //         sum--;
    //         ll rem = Y - i;
    //         if (sum < 0) {
    //             if (rem % abs(sum) == 0 && rem != 0) {
    //                 ans++;
    //                 ans %= mod;
    //             }
    //         }
    //     }
    //     cout << ans << "\n";
    // } else {
    //     ll ans = 1;
    //     ll sum = 0;
    //     for (ll i = 1; i <= X; ++i) {
    //         sum++;
    //         ll rem = X - i;
    //         if (rem % abs(sum) == 0 && rem != 0) {
    //             ans++;
    //             ans %= mod;
    //         }
    //     }
    //     cout << ans << "\n";
    // }
*/