计算题目复杂度时，请注意题目中 $n,m$ 等输入的总和有没有限制。

c++ 火车头参考见题解尾

A.他们说A题是最简单的

题意：

给定一个数组 $a$ ($1\le \left| a_i \right | \le 10^4$)，每次操作可以将某个 $a_i$ 变成 $-a_i$，问使得任意前缀和非负的最小操作次数。

知识点：

反悔贪心，贪心。

题解：

因为任意前缀和非负，不难想到从左往右检查。

为了使操作数最小，不难想到每次只翻转之前最大的几个数字。

可以使用优先队列、平衡树等实现。

时间复杂度 $(Tnlogn)$。

代码：

python:

import heapq

for _ in range(int(input())):
    s = 0
    ans = 0
    n = int(input())
    pq = []
    a = [0] + list(map(int, input().split()))
    for i in range(1, n+1):
        s += a[i]
        if a[i] < 0:
            heapq.heappush(pq, a[i])
        while s < 0 and pq:
            s -=  2 * heapq.heappop(pq)
            ans += 1
    print(ans)

C++:

void solve() {
    int n;
    cin >> n;
    vector<ll> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    priority_queue<ll> pq;
    ll sum = 0;
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        sum += a[i];
        if (a[i] < 0) pq.push(-a[i]);
        while (sum < 0 && !pq.empty()) {
            ll x = pq.top();
            pq.pop();
            sum += 2 * x;
            ++ans;
        }
    }
    cout << ans << "\n";
}

B.咕咕嘎嘎！

题意：

求只包含 $AUGC$ 四种字符长度为 $n$ 的字符串中至少出现一个 $\texttt{GUGUGAGA}$ 子串的概率。

知识点：

KMP自动机，dp，矩阵快速幂。

题解：

要求至少有一个的概率，我们可以先求一个都不包含的概率。

考虑已经匹配上前 $i$ 个字符后，再添加四种字符会使得匹配回到哪里。

可以列出以下矩阵，第 $i$ 行第 $j$ 列的元素代表已经匹配上前 $i$ 个字符后，有 $A_{i, j}$ 种方案使得加上后匹配了前 $j$ 个字符。

$$ A = \begin{pmatrix} 3 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \ 2 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \ 3 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \ 2 & 1 & 0 & 0 & 1 & 0 & 0 & 0 \ 3 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \ 1 & 1 & 0 & 0 & 1 & 0 & 1 & 0 \ 3 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \end{pmatrix}_{8 \times 8} $$

令

$$v = \begin{pmatrix} 1 \ 0 \ \vdots \ 0 \end{pmatrix}_{n \times 1} $$

则答案为 $A^n$ * $v$。

时间复杂度 $O(T{\left | P \right |}^3 logn)$（$P$ 为模式串）,预处理 $A$ 的 $2^n$ 次幂可以把时间压到 $500ms$左右。

代码：

手算矩阵

ll safeMul(ll x, ll y) {
    ll ans = 0;
    while (y) {
        if (y & 1) (ans += x) %= MOD;
        (x += x) %= MOD;
        y >>= 1;
    }
    return ans;
}

class Matrix {
public:
    vector<vector<ll>> g;
    ll col;
    ll row;

    Matrix(ll r, ll c) {
        col = c;
        row = r;
        g.clear();
        g.resize(r, vector<ll>(c));
    }

    Matrix(const Matrix& matrix) {
        row = matrix.row;
        col = matrix.col;
        g.clear();
        g.resize(row, vector<ll>(col));
        for (ll i = 0; i < row; i++) {
            for (ll j = 0; j < col; j++) {
                g[i][j] = matrix.at(i, j) % MOD;
            }
        }
    }

    void init(vector<vector<ll>> &matrix) {
        for (ll i = 0; i < row; i++) {
            for (ll j = 0; j < col; j++) {
                g[i][j] = matrix[i][j] % MOD;
            }
        }
    }

    Matrix operator *(const Matrix &matrix) {
        assert(col == matrix.row);
        Matrix ans(row, matrix.col);
        vector<vector<ll>> t(row, vector<ll>(matrix.col));
        for (ll i = 0; i < row; i++) {
            for (ll j = 0; j < matrix.col; j++) {
                for (ll k = 0; k < col; k++) {
                    t[i][j] = (t[i][j] + g[i][k] * matrix.g[k][j] % MOD) % MOD;
                    // t[i][j] = (t[i][j] + safeMul(g[i][k],matrix.g[k][j]))%MOD; //当爆ll时改下面的
                }
            }
        }
        ans.init(t);
        return ans;
    }

    Matrix operator *=(const Matrix &matrix) {
        assert(col == matrix.row);
        vector<vector<ll>> t(row, vector<ll>(matrix.col));
        for (ll i = 0; i < row; i++) {
            for (ll j = 0; j < matrix.col; j++) {
                for (ll k = 0; k < col; k++) {
                    t[i][j] = (t[i][j] + g[i][k] * matrix.g[k][j] % MOD) % MOD;
                    // t[i][j] = (t[i][j] + safeMul(g[i][k],matrix.g[k][j]))%MOD; //当爆ll时改下面的
                }
            }
        }
        col = matrix.col;
        g.clear();
        g.resize(row, vector<ll>(col));
        init(t);
        return *this;
    }

    Matrix copy() {
        Matrix other(row, col);
        other.init(g);
        return other;
    }

    PLL size() {
        return PLL{row, col};
    }

    ll at(ll x, ll y) {
        return g[x][y];
    }

    ll at(ll x, ll y) const {
        return g[x][y];
    }

    void print() {
        for (ll i = 0; i < row; i++) {
            for (ll j = 0; j < col; j++) {
                cout << g[i][j] << " ";
            }
            cout << "\n";
        }
        cout << "\n";
    }
};

Matrix makeE(ll n) {
    vector<vector<ll>> a(n, vector<ll>(n));
    for (ll i = 0; i < n; i++) a[i][i] = 1;
    Matrix res(n, n);
    res.init(a);
    return res;
}

Matrix matrixPow(Matrix &matrix, ll p) {
    assert(matrix.size().fi == matrix.size().se);
    Matrix res = makeE(matrix.size().fi);
    Matrix a = matrix.copy();
    while (p) {
        if (p & 1) {
            res *= a;
        }
        a *= a;
        p >>= 1;
    }
    return res;
}

Matrix ma(8, 8);
vector<Matrix> powm;

void init() {
    vector<vector<ll>> g = {
        {3, 1, 0, 0, 0, 0, 0, 0},
        {2, 1, 1, 0, 0, 0, 0, 0},
        {3, 0, 0, 1, 0, 0, 0, 0},
        {2, 1, 0, 0, 1, 0, 0, 0},
        {3, 0, 0, 0, 0, 1, 0, 0},
        {1, 1, 0, 0, 1, 0, 1, 0},
        {3, 0, 0, 0, 0, 0, 0, 1},
        {1, 1, 1, 0, 0, 0, 0, 0}
    };
    ma.init(g);
    powm.pb(ma);
    for (ll i = 1; i <= 63; i++) {
        powm.pb(powm.back() * powm.back());
    }
}

void solve() {
    ll n;
    cin >> n;
    if (n <= 7) {
        print(0);
    }
    else {
        Matrix mb = makeE(8);
        for (ll bit = 63; bit >= 0; bit--) {
            if ((n >> bit) & 1) {
                mb *= powm[bit];
            }
        }
        ll fz = 0;
        for (ll j = 0; j < 8; j++) {
            fz = (fz + mb.at(0, j)) % MOD;
        }
        cout << (1 - fz * ksm(ksm(4, n), MOD - 2) % MOD + MOD) % MOD << "\n";
    }
}

KMP自动机

template<int P>
struct MInt {
    int x;
    constexpr MInt() : x{} {}
    constexpr MInt(long long v) : x{norm(v % getMod())} {}

    static int Mod;
    constexpr static int getMod() {
        if (P > 0) return P;
        else return Mod;
    }
    constexpr static void setMod(int Mod_) {
        Mod = Mod_;
    }
    constexpr static int norm(long long v) {
        if (v < 0) v += getMod();
        if (v >= getMod()) v -= getMod();
        return int(v);
    }

    constexpr int val() const { return x; }
    explicit constexpr operator int() const { return x; }

    constexpr MInt operator-() const {
        return MInt(norm(getMod() - x));
    }

    constexpr MInt inv() const {
        assert(x != 0);
        return pow(getMod() - 2);
    }

    constexpr MInt pow(long long e) const {
        MInt res(1), base(*this);
        while (e > 0) {
            if (e & 1) res *= base;
            base *= base;
            e >>= 1;
        }
        return res;
    }

    constexpr MInt &operator*=(MInt rhs) & {
        x = int(1LL * x * rhs.x % getMod());
        return *this;
    }
    constexpr MInt &operator+=(MInt rhs) & {
        x = norm(x + rhs.x);
        return *this;
    }
    constexpr MInt &operator-=(MInt rhs) & {
        x = norm(x - rhs.x);
        return *this;
    }
    constexpr MInt &operator/=(MInt rhs) & {
        return *this *= rhs.inv();
    }

    friend constexpr MInt operator*(MInt lhs, MInt rhs) { return lhs *= rhs; }
    friend constexpr MInt operator+(MInt lhs, MInt rhs) { return lhs += rhs; }
    friend constexpr MInt operator-(MInt lhs, MInt rhs) { return lhs -= rhs; }
    friend constexpr MInt operator/(MInt lhs, MInt rhs) { return lhs /= rhs; }

    friend istream &operator>>(std::istream &is, MInt &a) {
        long long v;
        is >> v;
        a = MInt(v);
        return is;
    }
    friend ostream &operator<<(std::ostream &os, const MInt &a) {
        return os << a.val();
    }

    friend constexpr bool operator==(MInt lhs, MInt rhs) { return lhs.val() == rhs.val(); }
    friend constexpr bool operator!=(MInt lhs, MInt rhs) { return lhs.val() != rhs.val(); }
};

template<>
int MInt<0>::Mod = 998244353;

typedef MInt<MOD> Z;

template<int N>
struct Matrix {
    array<array<Z, N>, N> a;
    Matrix() {
        for (int i = 0; i < N; ++i)
            for (int j = 0; j < N; ++j)
                a[i][j] = Z(0);
    }
    static Matrix identity() {
        Matrix I;
        for (int i = 0; i < N; ++i) I.a[i][i] = Z(1);
        return I;
    }
    Matrix operator*(const Matrix &other) const {
        Matrix res;
        for (int i = 0; i < N; ++i) {
            for (int k = 0; k < N; ++k) {
                Z rik = a[i][k];
                if (rik.val() == 0) continue;
                for (int j = 0; j < N; ++j) {
                    res.a[i][j] += rik * other.a[k][j];
                }
            }
        }
        return res;
    }
    array<Z, N> operator*(const array<Z, N> &v) const {
        array<Z, N> res;
        for (int i = 0; i < N; ++i) {
            Z s = Z(0);
            for (int j = 0; j < N; ++j) {
                if (a[i][j].val() == 0 || v[j].val() == 0) continue;
                s += a[i][j] * v[j];
            }
            res[i] = s;
        }
        return res;
    }
};

struct KMP {
    string pattern;
    int L;
    vector<int> pi;
    vector<char> alph;
    KMP(const string &pat, const vector<char> dict) : pattern(pat), L(pat.size()), pi(L, 0), alph(dict) {
        for (int i = 1; i < L; ++i) {
            int j = pi[i - 1];
            while (j > 0 && pattern[i] != pattern[j]) j = pi[j - 1];
            if (pattern[i] == pattern[j]) ++j;
            pi[i] = j;
        }
    }
    Matrix<8> build() const {
        Matrix<8> M;
        for (int s = 0; s < L; ++s) {
            for (char ch : alph) {
                int ns = next(s, ch);
                if (ns < L) M.a[ns][s] += Z(1);
            }
        }
        return M;
    }
private:
    int next(int s, char ch) const {
        int k = s;
        while (k > 0 && pattern[k] != ch) k = pi[k - 1];
        if (pattern[k] == ch) ++k;
        return k;
    }
};

const int L = 8;
vector<char> dict = {'A', 'U', 'G', 'C'};
const string pattern = "GUGUGAGA";
KMP kmp(pattern, dict);
Matrix<L> base;
vector<Matrix<L>> POW(64);

void init() {
    base = kmp.build();
    POW[0] = base;
    for (int i = 1; i < 64; ++i) POW[i] = POW[i - 1] * POW[i - 1];
}

void solve() {
    ll n;
    cin >> n;
    if (n < L) {
        cout << 0 << "\n";
        return;
    }
    array<Z, L> v;
    for (int i = 0; i < L; ++i) v[i] = 0;
    v[0] = 1;

    ll x = n;
    int bit = 0;
    while (x) {
        if (x & 1ll) v = POW[bit] * v;
        x >>= 1;
        ++bit;
    }

    Z de(0);
    for (int i = 0; i < L; ++i) de += v[i];

    Z num = Z(4).pow(n);
    cout << (num - de) / num << "\n";
}

C. 勘探

题意：

问 $ n\times m$ 的网格中有多少个点 $(x, y)$，使得其与 $(1, 1)$ 的连线不会穿过除$(1, 1)$和$(x, y)$外的点

知识点：

莫比乌斯函数，莫比乌斯反演、容斥、整除分块。

题解：

不难想到问题等价于求有多少对整数使得 $gcd(i, j)=1$，即 $\sum \limits_{i=1}^{n} \sum \limits_{j=1}^{m} [gcd(i, j)=1]$。（$[]$ 为艾弗森括号, 若括号内等式成立则返回 $1$ , 否则返回 $0$ ）

莫比乌斯反演法：

预备知识：

数论函数：定义域为正整数的函数，如
单位函数：$\epsilon(n) = [n==1]。$
狄利克雷卷积：对于两个数论函数 $f(x)$ 和 $g(x)$ ，他们的狄利克雷卷积结果 $h(x)$ 定义为：$$h(x) = \sum \limits_{d|x}f(d)g(\frac{x}{d})=\sum \limits_{ab=x}f(a)g(b)$$可以简记为 $$h=f * g$$ 狄利克雷卷积满足交换律，结合律，分配律
莫比乌斯函数：
定义：$\mu(n)= \begin{cases}1, & n=1, \ 0, & n \text { 含有平方因子 } \ (-1)^k, & k \text { 为 } n \text { 的本质不同质因子个数 }\end{cases}$
性质：$\sum \limits_{d|n} \mu(d)= \begin{cases}1, & n=1, \ 0, & n \neq 1\end{cases}$ ，即 $\sum \limits_{d|n}\mu(d)=\epsilon(n),\mu * 1 = \epsilon$ ，证明如下
- 设 $n = \prod\limits_{i=1}^{k}p_i^{c_i},n’ = \prod\limits_{i=1}^{k}p_i$ ，那么 $\sum\limits_{d|n}\mu(d) = \sum\limits_{d|n’}\mu(d)=\sum\limits_{i=0}^k\binom{k}{i}·(-1)^i=(1+(-1))^k$ 。
- 根据二项式定理，易知该式子的值在 $k=0$ ，即 $n=1$ 时值为 $1$ ，否则为 $0$ ，即 $\sum \limits_{d|n}\mu(d)=\epsilon(n),\mu * 1 = \epsilon$ 。
推论：$[gcd(i, j)==1]=\sum\limits_{d|gcd(i,j)}\mu(d)$

因为 $gcd(i, j)=1$ 时对答案才有贡献，于是我们可以直接将其替换为 $\epsilon(gcd(i, j))$ ，故原式化为$$\sum \limits_{i=1}^{n} \sum \limits_{j=1}^{m} \epsilon(gcd(i, j))$$
将 $\epsilon$ 函数展开得到，$$\sum \limits_{i=1}^{n} \sum \limits_{j=1}^{m} \sum \limits_{d|gcd(i,j)}\mu(d)$$
变换求和顺序，先枚举 $d|gcd(i,j)$ 得到：$$\sum \limits_{d=1}\mu(d)\sum \limits_{i=1}^{n} [d|i]\sum \limits_{j=1}^{m} [d|j]$$
易知 $1\sim n$ 中 $d$ 的倍数有 $\lfloor \frac{n}{d}\rfloor$ 个，故原式化为 $$\sum \limits_{d=1}^{min(n,m)}\mu(d)\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor$$
很显然，式子可以用数论分块求解，时间复杂度 $O(n + T\sqrt{n})$ 。

容斥：

~~bro 莫比乌斯反演讲不明白就用容斥讲了~~

令 $ \mathcal{P} ={(x,y)∣1 \le x \le n,1 \le y \le m}$ ,$ \mathcal{G}={(x,y)\in \mathcal{P}∣gcd(x,y)=1}$。

令 $S_u = {(x, y)|(u|x \& u|y)}$，即满足 $x$，$y$ 均是 $u$ 的倍数的数对。易得 $ \left|S_u\right | = \lfloor \frac{n}{d} \rfloor * \lfloor \frac{m}{d} \rfloor$。

令 $\mu(d)= \begin{cases}1, & d=1, \ (-1)^{\omega(d)}, & d \text { 不含平方因子 } \omega(d) \text { 个素因子, } \ 0, & d \text { 含平方因子. }\end{cases}$

有 $ \mathcal{G}=\mathcal{P} \backslash \bigcup_{p \text { prime }} S_p$ ，即满足 $gcd(i, j)=1$ 的数对个数可以用全集减去 $i$，$j$ 均是质数的倍数的数对。

由容斥原理，有：

$\left|\bigcup_p S_p\right|=\sum_p\left|S_p\right|-\sum_{p<q}\left|S_p \cap S_q\right|+\sum_{p<q<r}\left|S_p \cap S_q \cap S_r\right|-\cdots .$

因此 $\left | \mathcal{G} \right | = \left | \mathcal{P} \right | – \left|\bigcup_p S_p\right|$ = $nm$ + $\sum\limits_{d=2}^{\infty} \mu(d)* \left|S_u\right |$。（所有含平方因子的数不在容斥中，不含平方因子的数的符号可以表示为 $(-1)^{\omega(d)}$）

注意到 $\mu{(1)} * \left | S_1 \right | = nm $ ，因此可以化为 $ \sum \limits_{d=1}^{\infty} \mu(d)\left\lfloor\frac{n}{d}\right\rfloor\left\lfloor\frac{m}{d}\right\rfloor$。

又因为 $d > min(n, m)$ 时，$\left | S_d \right | = 0$，因此可取上界 $min(n, m)$，即 $ \sum \limits_{i=1}^{n} \sum \limits_{j=1}^{m} [gcd(i, j)=1] = \sum \limits_{d=1}^{min(n, m)} \mu(d)\left\lfloor\frac{n}{d}\right\rfloor\left\lfloor\frac{m}{d}\right\rfloor$

$\mu{(d)}$ 可以用线性筛 $O(n)$ 求出，但是注意到 $min(n, m)$ 之和没有限制，因此需要用整除分块优化。

时间复杂度 $O(n + T\sqrt{n})$。

代码：

实现1:

vector<int> mu(maxn + 10), primes, spf(maxn + 10), pre(maxn + 10);

void init() {
    mu[1] = 1;
    for (int i = 2; i <= maxn; ++i) {
        if (!spf[i]) primes.push_back(i), spf[i] = i, mu[i] = -1;
        for (int j = 0; 1ll * i * primes[j] <= maxn; ++j) {
            int m = i * primes[j];
            spf[m] = primes[j];
            if (i % primes[j] == 0) {
                mu[m] = 0;
                break;
            } else {
                mu[m] = -mu[i];
            }
        }
    }

    for (int i = 1; i <= maxn; ++i) {
        pre[i] = pre[i - 1] + mu[i];
    }
}

void solve() {
    int n, m, r;
    cin >> n >> m;
    if (n > m) swap(n, m);
    ll ans = 0;

    for (int i = 1; i <= n; i = r + 1) {
        r = min(n / (n / i), m / (m / i));
        ans += (pre[r] - pre[i - 1]) * (ll)(n / i) * (m / i);
    }
    cout << ans << "\n";
}

实现2:

vector<ll> vis(maxn + 1), primes(1), mu(maxn + 1), sum(maxn + 1);

void init() {
    mu[1] = 1;
    for (ll i = 2; i <= maxn; i++) {
        if (!vis[i]) {
            primes.pb(i);
            mu[i] = -1;
        }
        for (ll j = 1; i * primes[j] <= maxn; j++) {
            ll m = i * primes[j];
            vis[m] = 1;
            if (i % primes[j] == 0) {
                mu[m] = 0;
                break;
            }
            else {
                mu[m] = - mu[i];
            }
        }
    }
    for (ll i = 1; i <= maxn; i++) {
        sum[i] = sum[i - 1] + mu[i];
    }
}

void solve() {
    ll n, m;
    cin >> n >> m;
    ll mx = min(n, m);
    ll l = 1, ans = 0, r;
    while (l <= mx) {
        ll tn = n / l;
        ll tm = m / l;
        r = min({mx, n / tn, m / tm});
        ans += (sum[r] - sum[l - 1]) * tn * tm;
        l = r + 1;
    }
    cout << ans << "\n";
}

D.进制转换

题意：

输入一个十进制数字 $n$ ，输出它在 $r$ 进制下的表示。

知识点：

取模，进制转化

题解：

正进制的转化很简单，其实负进制和正进制的转化是一样的。

注意要处理一下取模结果为负数的时候要加上 $\left | r \right |$。

代码：

python：

for _ in range(int(input())):
    n, r = map(int, input().split())
    if r > 0:
        s = []
        while n:
            s.append(str(n%r) if n % r < 10 else chr(ord('A')+(n%r-10)))
            n//=r
        print(''.join(s[::-1]))
    else:
        s = []
        while n:
            k = (n % r - r)%(-r)
            s.append(str(k) if k < 10 else chr(ord('A')+(k-10)))
            n = (n-k)//r
        print(''.join(s[::-1]))

C++:

void solve() {
    int n, r;
    cin >> n >> r;
    vector<int> a;
    while (n) {
        int t = n % r;
        n /= r;
        if (t < 0) {
            t = t + abs(r);
            n++;
        }
        a.pb(t);
    }
    for (int i = a.size() - 1; i >= 0; --i) {
        if (a[i] < 10) cout << a[i];
        else cout << (char)(a[i] - 10 + 'A');
    }
    cout << "\n";
}

E.Renewable Natural Gas

题意：

构造一个大小为 $n$ 的数组 $v$，满足以下条件。

给定你三个大小为 $m$ 的数组 $a$，$b$，$c$ ，对于任意的 $1\le i \le m$, 满足 $v_{a_i} \oplus v_{b_i} \ne v_{c_i}$。
没有重复出现的数字，即 $v_1 \ne v_2 \ne \dots \ne v_n$。
对于任意的 $1\le i \le n$, 满足 $0 \le v_i \le 10^{18}$

知识点：

随机数

题解：

本题其实是一道诈骗题，输出 $n$ 个 $[0, 10^{18}]$ 的随机数即可通过。

具体原因其实是异或哈希的前置。在异或哈希中，我们需要找到一系列数字，使得其中任意一些数字的异或和不是另一个数字。

如果随机生成 $n$ 个数字，冲突的概率大概为 $ \frac{n^2}{10^{18}}$，实际上很小，可以忽略不计。

由于本题只要求 $v_{a_i} \oplus v_{b_i} \ne v_{c_i}$，有非随机数的解法。

时间复杂度 $O(n)$。

代码：

python:

import random
n, m = map(int, input().split())
print(*[random.randint(0, 10**18) for _ in range(n)])

C++（带了个验证）:

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(m), b(m), c(m);
    for (auto &v : a) cin >> v;
    for (auto &v : b) cin >> v;
    for (auto &v : c) cin >> v;

    mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
    uniform_int_distribution<ll> dist(0, (ll)1e18);

    vector<ll> v(n + 1);
    unordered_set<ll> S;

    while (true) {
        S.clear();
        for (int i = 1; i <= n; i++) {
            ll x;
            do {
                x = dist(rng);
            } while (S.count(x));
            S.insert(x);
            v[i] = x;
        }

        bool ok = true;
        for (int i = 0; i < m; i++) {
            if ((v[a[i]] ^ v[b[i]]) == v[c[i]]) {
                ok = false;
                break;
            }
        }
        if (ok) break;
    }

    for (int i = 1; i <= n; i++) {
        cout << v[i] << " ";
    }
    cout << "\n";
}

F.小学奥数题

题意：

现有 $n$ 个人排成一排，每个人头上带了一个牌子。对于第 $i$ 个人，他看的见其余 $n-1$ 个人的牌子是什么颜色的，但看不见自己的牌子是什么颜色的。

你会向每个人询问：你能看见的牌子中不同颜色中出现最多次数的颜色的出现次数是多少？

给你一个大小为 $n$ 的数组 $v$， $v_i$ 代表第 $i$ 个人的回答。

你要构造一个数组 $a_i$ ，满足每个人的回答 , $a_i$ 代表第 $i$ 个人的颜色。如果可能，输出 $\texttt{YES}$，并输出数组 $a$。否则输出 $\texttt{NO}$。

为方便输出，本题中用整数代表颜色（$1\le a_i \le 2 \times 10^5$）。数值相同认为颜色相同，数值不同认为颜色不同。

知识点：

~~小学奥数~~

题解：

不妨考虑不同的数组 $a$ 对应的数组 $v$ 有什么特点。

手玩一下不难发现，每个人的回答只跟出现次数最多的两个数字的出现次数有关。

令出现次数最多的数字出现了 $f_1$ 次，颜色为 $c_1$ 。次多的出现了$f_2$ 次。，颜色为 $c_2$ 。

若 $f1 = f2$ ，则每个人的回答都为 $f_1$。因为对于颜色不为 $c_1$ 、 $c_2$ 的人，其答案显然为$f_1$；对颜色为$c_1$ 或 $c_2$ 的人，此时另一种颜色的出现次数成为最大值，答案也为 $f_1$。
若 $f1 = f2 + 1$，则对于颜色不为 $c_1$的人，其答案显然为$f_1$；对颜色为$c_1$ 的人，此时最大值变为 $f1 – 1 = f2$，答案为 $f_2$。
其余情况下，每个人的答案均为 $f_1$。因为对于每个人来说，$c_1$ 都是出现次数最多的颜色。

整理可得，$v$ 的特点如下：

所有数字均相等，且 $\le \frac{n}{2}$
所有数字均相等，且为 $n-1$
出现的两种数字，$a, b$，且 $b = a – 1$ 、$a$ 出现了 $b$ 次。

对于第一种情况，我们每 $v_0$ 个人换一种颜色即可。

对于第二种情况，我们让所有人都是同一种颜色即可。

对于第三种情况，我们让所有回答 $b$ 的人颜色为 $1$ ，其余人每 $a$ 个人一种颜色即可。

时间复杂度 $O(n)$，我偷了个懒到了 $O(nlogn)$。

代码：

python:

for _ in range(int(input())):
    n = int(input())
    v = list(map(int, input().split()))
    if len(set(v)) == 1:
        if v[0] <= n//2:
            print("YES")
            print(*[i//v[0]+1 for i in range(n)])
        elif v[0] == n-1:
            print("YES")
            print(*[1 for i in range(n)])
        else:
            print("NO")
    elif len(set(v)) == 2:
        vv = v[:]
        v.sort()
        c1 = v.count(v[0])
        c2 = v.count(v[-1])
        if c1 == v[-1] and v[-1] - v[0] == 1:
            print("YES")
            a = [0 for i in range(n)]
            cnt = 0
            for i in range(n):
                if vv[i] == v[0]:
                    a[i] = 1
                else:
                    a[i] = cnt//v[0] + 2
                    cnt += 1
            print(*a)
        else:
            print("NO")
    else:
        print("NO")

C++:

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> cnt(n + 1);
    for (auto &v : a) cin >> v, cnt[v]++;

    vector<int> b = a;
    sort(all(a));
    a.erase(unique(all(a)), a.end());
    if (a.size() == 1) {
        if (a[0] <= n / 2 || a[0] == n - 1) {
            cout << "YES" << "\n";
            if (a[0] == n - 1) {
                for (int i = 0; i < n; ++i) {
                    cout << 1 << " ";
                }
                cout << "\n";
            } else {
                for (int i = 0; i < a[0]; ++i) {
                    cout << 1 << " " << 2 << " ";
                }
                for (int i = 0; i < n - 2 * a[0]; ++i) {
                    cout << i + 3 << " ";
                }
                cout << "\n";
            }
        } else {
            cout << "NO" << "\n";
        }
    } else if (a.size() > 2) {
        cout << "NO" << "\n";
    } else {
        if (a[1] - a[0] == 1 && cnt[a[0]] == a[1]) {
            cout << "YES" << "\n";
            int c = 2;
            for (int i = 0; i < n; ++i) {
                if (b[i] == a[0]) cout << 1 << " ";
                else cout << c++ << " ";
            }
            cout << "\n";
        } else {
            cout << "NO" << "\n";
        }
    }
}

G.回文串

题意：

给定一系列字符，问能不能组成一个回文串。

知识点：

回文串

题解：

统计所有字符出现的次数，如果出现奇数次的字符数量不超过 $1$，则可以。

时间复杂度 $O(Tn)$。

代码：

python:

import random
v = {chr(i):random.randint(0, 10**18) for i in range(ord('A'), ord('Z')+1)}
v.update({chr(i):random.randint(0, 10**18) for i in range(ord('a'), ord('z')+1)})
vv = {v[k]:k for k in v}
for _ in range(int(input())):
    n = int(input())
    c = input().strip().split()
    s = 0
    for i in c:
        s ^= v[i]
    if s == 0 or s in vv:
        print("YES")
    else:
        print("NO")

C++:

void solve() {
    vector<int> a(26);
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        char c;
        cin >> c;
        a[c - 'A']++;
    }
    int cnt = 0;
    for (auto v : a) {
        if (v & 1) {
            cnt++;
        }
    }
    if (cnt == 1 && n & 1 || cnt == 0) {
        cout << "YES" << "\n";
    } else {
        cout << "NO" << "\n";
    }
}

H.G-C-D

题意：

给出长度为 $n$ 的两个数组 $p$
和 $s$ ，其中 $p$ 是某个数组 $a$ 的前缀 $GCD ^∗$，而 $s$ 是同一个数组 $a$ 的后缀 $GCD$。换句话说，如果数组 $a$ 存在，那么对于每个 $1≤i≤n$ ，下面的等式都成立：

$p_i = gcd(a_1,a_2,…,a_i)$
$s_i = gcd(a_i, a_{i+1}, \dots, a_n)$
$1\le a_i \le 2^{63}-1$

判断是否存在这样的数组 $a$ ，可以得到给定的数组 $p$ 和 $s$ 。

知识点：

gcd

题解：

$p$, $s$ 为前/后缀 gcd，因此一定有 $p_{i+1}|p_{i}$, $s_{i}|s_{i+1}$。

此外，所有数字的 gcd一定是定值，因此 $gcd{p_i, s_{i+1}}$ 的值是同一个。

如果不满足以上条件，则输出 $NO$。

考虑如何复原 $a_i$。

我们已经知道 $s_i$, $p_i$，则 $s_i|a_i$， $p_i|a_i$。

所以可以取 $a_i = lcm(s_i, p_i)$。

时间复杂度 $O(n)$。

代码:

python:

from math import gcd

def solve():
    n = int(input())
    p = [0] + list(map(int, input().split())) + [0]
    s = [0] + list(map(int, input().split())) + [0]
    for i in range(2, n+1):
        if p[i-1]%p[i]:
            print("NO")
            return
    for i in range(1, n):
        if s[i+1] % s[i]:
            print("NO")
            return
    g = s[1]
    for i in range(1, n+1):
        if gcd(p[i], s[i+1]) != g:
            print("NO")
            return
    print("YES")
    a = [0 for i in range(n+2)]
    for i in range(1, n+1):
        a[i] = p[i] * s[i]//gcd(p[i], s[i])
    print(*a[1:n+1])


for _ in range(int(input())):
    solve()

C++:

void solve() {
    int n;
    cin >> n;
    vector<ll> p(n), s(n);
    for (int i = 0; i < n; ++i) cin >> p[i];
    for (int i = 0; i < n; ++i) cin >> s[i];
    vector<ll> ans(n);
    for (int i = 0; i < n; ++i) {
        ans[i] = lcm<ll>(p[i], s[i]);
    }
    int g = 0;
    for (int i = 0; i < n; ++i) {
        g = gcd(g, ans[i]);
        if (g != p[i]) {
            cout << "NO" << "\n";
            return;
        }
    }
    g = 0;
    for (int i = n - 1; i >= 0; --i) {
        g = gcd(g, ans[i]);
        if (g != s[i]) {
            cout << "NO" << "\n";
            return;
        }
    }
    cout << "YES" << "\n";
    for (int i = 0; i < n; ++i) {
        cout << ans[i] << " ";
    }
    cout << "\n";
}

I.纳西妲喜欢枣椰蜜糖

题意：

给定一系列点，问能不能选取 $3$ 个点组成一个三角形。

知识点：

模拟

题解：

暴力枚举每三个点，判断是不是三角形即可。

时间复杂度 $O(Tn^3)$

代码：

python:

def solve():
    n = int(input())
    p = [list(map(int, input().split())) for _ in range(n)]
    for i in range(n):
        for j in range(i+1, n):
            for k in range(j+1, n):
                a = [p[i][0]-p[j][0], p[i][1]-p[j][1]]
                b = [p[k][0]-p[j][0], p[k][1]-p[j][1]]
                if a[0] * b[1] - b[0] * a[1] != 0:
                    print("YES")
                    print(*p[i])
                    print(*p[j])
                    print(*p[k])
                    return
    print("NO")

for _ in range(int(input())):
    solve()

C++

void solve() {
    ll n;
    cin >> n;
    vector<PLL> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i].fi >> a[i].se;
    }
    double k;
    if (a[1].se == a[0].se) k = INF;
    else k = 1.0 * (a[1].fi - a[0].fi) / (a[1].se - a[0].se);
    for (int i = 2; i < n; ++i) {
        if (1.0 * (a[i].fi - a[1].fi) / (a[i].se - a[1].se) != k) {
            cout << "YES" << "\n";
            cout << a[0].fi << " " << a[0].se << "\n";
            cout << a[1].fi << " " << a[1].se << "\n";
            cout << a[i].fi << " " << a[i].se << "\n";
            return;
        }
    }
    cout << "NO" << "\n";
    return;
}

J.物资调配

题意：

给定长度为 $n$ 的数组，有以下两个操作：

对所有 $i \in[l, r]$ 执行 $a_i \leftarrow a_i+x_{\circ}$
求 $\min{\sum_{i=l}^r\left|a_i-y\right| }$，$y$ 为任意正数。

知识点：

块状数组、分块

题解：

块状数组板子题。

对于操作二，易得 $y$ 取 $[l, r]$ 的中位数最优。

时间复杂度 $O(n\sqrt{n}logINF)$

代码：

实现1：

void solve() {
    int n, q;
    cin >> n >> q;
    vector<ll> a(n);
    int B = sqrt(n);
    int N = (n + B - 1) / B;
    vector<ll> lazy(N), idx(n);
    vector<vector<ll>> block(N);
    for (int i = 0; i < n; ++i) cin >> a[i], idx[i] = i / B;
    auto rebuild = [&](int I) {
        int st = I * B, ed = min((I + 1) * B, n);
        if (lazy[I] != 0) {
            for (int i = st; i < ed; ++i) a[i] += lazy[I];
            lazy[I] = 0;
        }
        block[I].assign(a.begin() + st, a.begin() + ed);
        sort(all(block[I]));
    };
    auto update = [&](int l, int r, ll x) {
        int L = idx[l], R = idx[r];
        if (L == R) {
            rebuild(L);
            for (int i = l; i <= r; ++i) a[i] += x;
            rebuild(L);
        } else {
            rebuild(L);
            for (int i = l; i < (L + 1) * B; ++i) a[i] += x;
            rebuild(L);

            for (int i = L + 1; i < R; ++i) lazy[i] += x;

            rebuild(R);
            for (int i = R * B; i <= r; ++i) a[i] += x;
            rebuild(R);
        }
    };
    auto count = [&](int l, int r, ll val) {
        int L = idx[l], R = idx[r];
        int count = 0;
        if (L == R) {
            for (int i = l; i <= r; ++i) if (a[i] + lazy[L] <= val) count++;
        } else {
            for (int i = l; i < (L + 1) * B; ++i) if (i >= l && a[i] + lazy[L] <= val) count++;
            for (int i = L + 1; i < R; ++i) {
                count += upper_bound(all(block[i]), val - lazy[i]) - block[i].begin();
            }
            for (int i = R * B; i <= r; ++i) if (i <= r && a[i] + lazy[R] <= val) count++;
        }
        return count;
    };
    auto query = [&](int l, int r) {
        int len = r - l + 1;
        ll rk = (len + 1) / 2;
        ll lo = -INF, hi = INF, med = -INF;
        while (lo <= hi) {
            ll mid = lo + (hi - lo) / 2;
            if (count(l, r, mid) >= rk) {
                med = mid;
                hi = mid - 1;
            } else lo = mid + 1;
        }

        ll cost = 0;
        int L = idx[l], R = idx[r];
        if (L == R) {
            for (int i = l; i <= r; ++i) cost += llabs((a[i] + lazy[L]) - med);
        } else {
            for (int i = l; i < (L + 1) * B; ++i) if (i >= l) cost += llabs((a[i] + lazy[L]) - med);
            for (int i = L + 1; i < R; ++i) {
                for (ll v : block[i]) cost += llabs((v + lazy[i]) - med);
            }
            for (int i = R * B; i <= r; ++i) if (i <= r) cost += llabs((a[i] + lazy[R]) - med);
        }
        return cost;
    };

    for (int i = 0; i < N; ++i) rebuild(i);
    while (q--) {
        int op, l, r;
        cin >> op >> l >> r;
        if (op == 1) {
            ll x;
            cin >> x;
            update(l - 1, r - 1, x);
        } else {
            cout << query(l - 1, r - 1) << "\n";
        }
    }
}

实现2::

void solve() {
    ll n, q;
    cin >> n >> q;
    vector<ll> a(n + 1);
    for (ll i = 1; i <= n; i++) cin >> a[i];
    ll B = sqrt(n);
    ll nB = (n + B - 1) / B;
    vector<ll> L(nB), R(nB), id(n + 1);
    for (ll b = 0; b < nB; b++) {
        L[b] = b * B + 1;
        R[b] = min(n, (b + 1) * B);
    }
    for (ll i = 1; i <= n; i++) {
        id[i] = (i - 1) / B;
    }
    vector<vector<ll>> sorted(nB);
    vector<vector<ll>> pre(nB);
    vector<ll> lazy(nB);

    function<void(ll)> build = [&](ll b) {
        sorted[b].clear();
        for (ll i = L[b]; i <= R[b]; i++) {
            sorted[b].pb(a[i]);
        }
        sort(all(sorted[b]));
        pre[b].clear();
        if (!sorted[b].empty()) {
            pre[b].pb(sorted[b][0]);
            for (ll i = 1; i < (ll)sorted[b].size(); i++) {
                pre[b].pb(pre[b][i - 1] + sorted[b][i]);
            }
        }
    };
    function<void(ll)> push_down = [&](ll b) {
        if (!lazy[b]) return;
        for (ll i = L[b]; i <= R[b]; i++) a[i] += lazy[b];
        lazy[b] = 0;
        build(b);
    };
    function<ll(ll, ll, ll)> countle = [&](ll l, ll r, ll v) {
        ll bl = id[l], br = id[r];
        ll ans = 0;
        if (bl == br) {
            for (ll i = l; i <= r; i++) ans += (a[i] + lazy[bl] <= v);
            return ans;
        }
        for (ll i = l; i <= R[bl]; i++) ans += (a[i] + lazy[bl] <= v);
        for (ll i = L[br]; i <= r; i++) ans += (a[i] + lazy[br] <= v);
        for (ll b = bl + 1; b <= br - 1; b++) {
            ll t = v - lazy[b];
            ans += upper_bound(all(sorted[b]), t) - sorted[b].begin();
        }
        return ans;
    };
    function<ll(ll, ll, ll)> sumle = [&](ll l, ll r, ll v) {
        ll bl = id[l], br = id[r];
        ll ans = 0;
        if (bl == br) {
            for (ll i = l; i <= r; i++) if (a[i] + lazy[bl] <= v) ans += a[i] + lazy[bl];
            return ans;
        }
        for (ll i = l; i <= R[bl]; i++) if (a[i] + lazy[bl] <= v) ans += a[i] + lazy[bl];
        for (ll i = L[br]; i <= r; i++) if (a[i] + lazy[br] <= v) ans += a[i] + lazy[br];
        for (ll b = bl + 1; b <= br - 1; b++) {
            ll t = v - lazy[b];
            ll c = upper_bound(all(sorted[b]), t) - sorted[b].begin();
            if (c) ans += pre[b][c - 1] + c * lazy[b];
        }
        return ans;
    };
    function<ll(ll, ll)> sum = [&](ll l, ll r) {
        ll bl = id[l], br = id[r];
        ll ans = 0;
        if (bl == br) {
            for (ll i = l; i <= r; i++) ans += a[i] + lazy[bl];
            return ans;
        }
        for (ll i = l; i <= R[bl]; i++) ans += a[i] + lazy[bl];
        for (ll i = L[br]; i <= r; i++) ans += a[i] + lazy[br];
        for (ll b = bl + 1; b <= br - 1; b++) {
            if (!pre[b].empty()) ans += pre[b].back() + (ll)pre[b].size() * lazy[b];
        }
        return ans;
    };
    function<void(ll, ll, ll)> add = [&](ll l, ll r, ll v) {
        ll bl = id[l], br = id[r];
        if (bl == br) {
            push_down(bl);
            for (ll i = l; i <= r; i++) a[i] += v;
            build(bl);
            return;
        }
        push_down(bl);
        for (ll i = l; i <= R[bl]; i++) a[i] += v;
        build(bl);
        push_down(br);
        for (ll i = L[br]; i <= r; i++) a[i] += v;
        build(br);
        for (ll b = bl + 1; b <= br - 1; b++) lazy[b] += v;
    };
    function<ll(ll, ll)> query = [&](ll l, ll r) {
        ll len = r - l + 1;
        ll k = (len + 1) / 2;
        ll le = -INF, ri = INF;
        while (le < ri) {
            ll m = le + (ri - le) / 2;
            if (countle(l, r, m) >= k) ri = m;
            else le = m + 1;
        }
        ll mid = le;
        ll cnt1 = countle(l, r, mid);
        ll sum1 = sumle(l, r, mid);
        ll tot = sum(l, r);
        ll cnt2 = len - cnt1;
        ll sum2 = tot - sum1;
        return sum2 - cnt2 * mid + cnt1 * mid - sum1;
    };

    for (ll b = 0; b < nB; b++) build(b);
    while (q--) {
        ll op;
        cin >> op;
        if (op == 1) {
            ll l, r, x;
            cin >> l >> r >> x;
            add(l, r, x);
        }
        else {
            ll l, r;
            cin >> l >> r;
            print(query(l, r));
        }
    }
}

K.The Nether

题意：

给定一个有向无环图，定义 $f(i)$ 为从 $i$ 出发的最大路径长度，求 $\sum \limits_{i=1}^{n} f(i) * i$，答案对 $998244353$ 取模。

知识点：

拓扑排序、dp

题解：

在反图上做拓扑排序并dp，有 $dp_v = max{dp_u+1}$，统计答案即可。

时间复杂度 $O(n)$。

代码：

python:

MOD = 998244353
from collections import deque
for _ in range(int(input())):
    n, m = map(int, input().split())
    g = [[] for i in range(n+1)]
    idg = [0 for i in range(n+1)]
    for _ in range(m):
        u, v= map(int, input().split())
        g[v].append(u)
        idg[u]+=1
    f = [0 for i in range(n+1)]
    q = deque()
    for i in range(1, n+1):
        if idg[i] == 0:
            f[i] = 1
            q.append(i)

    while q:
        u = q.popleft()
        for v in g[u]:
            f[v] = max(f[v], f[u]+1)
            idg[v]-=1
            if not idg[v]:
                q.append(v)
    ans = 0
    for i in range(1, n+1):
        ans = (ans + i * f[i])%MOD
    print(ans)

C++:

void solve() {
    ll n, m;
    cin >> n >> m;
    vector<vector<ll>> g(n + 1);
    vector<ll> idg(n + 1);
    for (ll i = 1; i <= m; i++) {
        ll u, v;
        cin >> u >> v;
        g[v].pb(u);
        idg[u]++;
    }
    queue<ll> q;
    vector<ll> ans(n + 1);
    for (ll i = 1; i <= n; i++) {
        if (idg[i] == 0) {
            q.push(i);
            ans[i] = 1;
        }
    }
    while (q.size()) {
        ll u = q.front();
        q.pop();
        for (auto v : g[u]) {
            idg[v]--;
            ans[v] = max(ans[v], ans[u] + 1);
            if (idg[v] == 0) {
                q.push(v);
            }
        }
    }
    ll nhd = 0;
    for (ll i = 1; i <= n; i++) {
        nhd = (nhd + ans[i] * i) % MOD;
    }
    cout << nhd << "\n";
}

L.Wrong Answer on test 10

题意：

输出第 $n$ 个质数，$1\le n \le 4 \times 10^5$。

知识点：

质数筛

题解：

质数筛板子题，原理其实小学就学过，即划掉 $2、3、5、7、11 \dots$ 的倍数。

需要注意第 $4 \times 10^5$ 个质数为 $5800079$，记得检查有没有筛出足够个数的质数。

时间复杂度 $O(nloglogn)$ 或 $O(n)$。

代码：

python:

d = [i for i in range(6*10**6+1)]
p = [0]
for i in range(2,6*10**6):
    if d[i] != i:
        continue
    p.append(i)
    for j in range(i,6*10**6,i):
        d[j] = i

for _ in range(int(input())):
    print(p[int(input())])

C++:

vector<int> primes;

void init() {
    int maxn = 6e6;
    vector<bool> vis(maxn + 1);
    for (int i = 2; i <= maxn; ++i) {
        if (!vis[i]) {
            primes.pb(i);
            for (int j = i + i; j <= maxn; j += i) {
                vis[j] = 1;
            }
        }
    }
}

void solve() {
    int n;
    cin >> n;
    cout << primes[n - 1] << "\n";
}

M.我补药学数论口牙

题意：

给你一个字符串，你可以任意重组这个字符串，使得重组后的字符串没有 $FFT$ 和 $NTT$ 子串。

知识点：

模拟

题解：

d2A原题

注意到把所有的 $T$ 放到开头，一定重组后的字符串没有 $FFT$ 和 $NTT$ 子串。（排序后也行）

时间复杂度 $O(n)$ 或 $O(nlogn)$ 。

但是要小心 python 由于字符串是不可变对象，如果字符串加法过多会导致时间复杂度退化到 $O(n^2)$。

代码：

python:

for _ in range(int(input())):
    n = int(input())
    s = input().strip()
    print("".join(sorted(s, key=lambda x:-ord(x))))

C++:

void solve() {
    ll n;
    cin >> n;
    string s;
    cin >> s;
    ll c1 = 0;
    for (ll i = 0; i < s.size(); i++) {
        if (s[i] == 'T') c1++;
    }
    for (ll i = 1; i <= c1; i++) {
        cout << 'T';
    }
    for (ll i = 0; i < s.size(); i++) {
        if (s[i] != 'T') cout << s[i];
    }
    cout << "\n";
}

头文件

//Another
#include<bits/stdc++.h>
#include<bits/extc++.h>
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef tuple<ll, ll, ll> TLLL;
typedef __gnu_pbds::tree<PLL, __gnu_pbds::null_type, less<PLL>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> Tree;
// typedef __gnu_pbds::tree<ll, __gnu_pbds::null_type, less<ll>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> Tree;

constexpr int inf = (ll)1e9 + 7;
constexpr ll INF = (ll)2e18 + 9;
// constexpr ll INF = (ll)4e18;
// constexpr ll MOD = 1e9 + 7;
constexpr ll MOD = 998244353;
constexpr ld PI = acos(-1.0);
constexpr ld eps = 1e-10;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ull randint(ull l, ull r) {uniform_int_distribution<unsigned long long> dist(l, r); return dist(rng);}

void init() {

}

void solve() {

}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    init();

    int t = 1;
    cin >> t;
    for (int _ = 1; _ <= t; ++_) {
        solve();
    }
    return 0;
}