详细写了A-C的题解原博客题解地址：https://zhuanlan.zhihu.com/p/687290524

A题

不难发现前者除了 $n=2$ 的时，其余时候均有 $\sum_{i=1}^n i\le \prod_{i=1}^n i$ 。

容易得到 $\sum_{i=1}^n i=\dfrac{n(n 1)}{2}$ 。

小范围的时候 $n\le 10$ ，我们直接暴力计算二者的 $\gcd$ 。

不妨设前者为 $a$ ，后者为 $b$ 。

当范围大起来之后，我们进行分类讨论。

若 $n$ 为奇数
- 则 $\dfrac{n 1}{2}$ 时在 $1\sim n$ 之中，此时 $a$ 对应的两个数均包含在 $b$ 中；
- 故此时答案为 $a$ 。
若 $n$ 为偶数
- 显然 $\dfrac{n}{2}$ 会被包含在 $1\sim n$ 之中；
- 我们对 ${n 1}$ 做质因数分解。
  - 若其为质数，则不能贡献 $\gcd$ ，答案为 $\dfrac{n}{2}$ 。
  - 否则，若是质数的平方，则只能贡献一个 $\sqrt{n 1}$ ，答案为 $\dfrac{n\sqrt{n 1}}{2}$
  - 若不是，则 $n 1$ 可以分解为两个均大于 $1$ 的不同的数，答案为 $a$ 。

#include <bits/stdc++.h>
using namespace std;

#define debug(x) cerr << #x << ": " << x << '\n';
#define bd cerr << "----------------------" << el;
#define el '\n'
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define lop(i, a, b) for (int i = (a); i < (b); i++)
#define dwn(i, a, b) for (int i = (a); i >= (b); i--)
#define cmax(a, b) a = max(a, b)
#define cmin(a, b) a = min(a, b)
#define x first
#define y second
#define db double

typedef long long LL;
typedef pair<int, int> PII;

constexpr int N = 2e6 + 10, md = 1e9 + 7;
constexpr int INF = 0x3f3f3f3f;

int n, m;

LL sum(LL n)
{
    return (n + 1) * n / 2;
}
LL bf(int n)
{
    LL a = sum(n);
    LL b = 1;
    rep(i, 2, n)
    {
        b *= i;
    }
    // debug(a);
    // debug(b);
    return __gcd(a, b);
}

LL solve(int n)
{
    // cin >> n;
    if(n <= 10)
    {
        return bf(n);
    }
    else {
        if(n & 1)
        {
            return sum(n) ;
        }
        else {
            LL a = n / 2;
            LL b = (n + 1);
            bool flag = false;
            int sq = sqrt(b);
            
            for(int i = 2; i * i <= b; i ++)
            {
                if(b % i == 0)
                {
                    flag = true;
                    break;
                }
            }
            // debug(flag);
            if(flag == false)
            {//质数
                return a;
            }
            else { //合数
                flag = false;
                for(int i = 2; i * i < b; i ++)
                {
                    if(b % i == 0)
                    {
                        flag = true;
                        break;
                    }
                }
                if(!flag)
                {//gcd只能贡献一个sq
                    a *= sq;
                    return a;
                }  
                else {
                    return sum(n) ;
                }
            }
        }
    }
}

int main()
{
    cin.tie(0)->sync_with_stdio(false);
    cout.tie(0);
    cin >> n;
    cout << solve(n);
}

B题

对于字典序，不难想到贪心来做，前面的字典序越小越好。

我们可以以距离为标准，将每个位置看成一个节点，相同节点的在同一层，弄成一个分层图。

显然只有一个节点是，一层里面字典序最小的，他才可以当做起点去更新后一层。

我写的时候，一直内层超限，最后我用 short 来替代了int 解决这个问题。

中途猪比了，没有标记一个状态访问过，然后复杂度就成指数级，此时TLE了

#include <bits/stdc++.h>
using namespace std;

#define debug(x) cerr << #x << ": " << x << '\n';
#define bd cerr << "----------------------" << el;
#define el '\n'
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define lop(i, a, b) for (int i = (a); i < (b); i++)
#define dwn(i, a, b) for (int i = (a); i >= (b); i--)
#define cmax(a, b) a = max(a, b)
#define cmin(a, b) a = min(a, b)
#define x first
#define y second
#define db double

typedef long long LL;
typedef pair<int, int> PII;

constexpr int N = (1 << 10) + 2, md = 1e9 + 7;
constexpr int INF = 0x3f3f3f3f;

int n, m;
string s[N];
string ans;
// char a[N][N], last[N][N];
char mi[3 * N];
bool vis[N][N];
// short dis[N][N];
void solve()
{
    memset(mi, 127, sizeof mi);
    char inf = mi[0];
    cin >> n >> m;
    lop(i, 0, n)
    {
        cin >> s[i];
    }

    // ans += s[0][0];
    mi[0] = s[0][0];
    queue<array<short, 3>> q;
    q.push({0, 0, 0});
    while (q.size())
    {
        auto [x, y, dis] = q.front();
        q.pop();
        if (s[x][y] != mi[dis])
            continue;
        int vx = x, vy = y + 1; // 向右
        if (vy < m)
        {
            if (mi[dis + 1] > s[vx][vy])
            {
                mi[dis + 1] = s[vx][vy];
            }
            if (mi[dis + 1] == s[vx][vy] && !vis[vx][vy])
            {
                vis[vx][vy] = true;
                q.push({vx, vy, dis + 1});
            }
        }
        vx = x + 1, vy = y;
        if (vx < n)
        {
            if (mi[dis + 1] > s[vx][vy])
            {
                mi[dis + 1] = s[vx][vy];
            }
            if (mi[dis + 1] == s[vx][vy] && !vis[vx][vy])
            {
                vis[vx][vy] = true;
                q.push({vx, vy, dis + 1});
            }
        }
    }
    int j = 0;
    while (1)
    {
        if (mi[j] == inf)
            break;
        ans += mi[j];
        j++;
        // assert(j <= 4e6);
    }
    assert(ans.size() == n + m - 1);
    cout << ans;
}

int main()
{
    cin.tie(0)->sync_with_stdio(false);
    cout.tie(0);
    solve();
}

C题

可以发现 $L_1$ 是这样一个序列： $a b,2a b,3a b,4a b,\cdots$

我们发现 $a,b$ 的计算是正交的，所以其实我们可以拆开算 $a,b$ ，只看他们的系数，最后分别乘以 $a,b$ 即可。

于是 $L_1$ 的 $a$ 就是 $1,2,3,4,\cdots$ ，其的 $b$ 就是 $1,1,1,1,\cdots$

我们再把 $b$ 系数做一次前缀和对应 $L_2$ ，就可以发现变成了 $1,2,3,4,\cdots$

所以二者可以用同一套计算方式来计算，只不过是偏差了一个维度。

那么 $1,1,1,1,\cdots$ 这个序列的多次前缀和的结果是什么呢？

约定 $n$ 从 $1$ 开始：

零次， $C_n^0$ ，
一次， $C_n^1$
两次， $C_{n 1}^2$
三次， $C_{n 2}^3$
四次， $C_{n 3}^4$

为什么？因为初始序列，不难发现，初始序列的通项公式是 $C_n^0$ 。

我在 GhostLX：算法学习笔记(8)：组合数学基础中的性质10提到过：

\begin{eqnarray}\sum_{i=k}^n\dbinom{i}{k} = \dbinom{n 1}{k 1}\tag{10}\end{eqnarray}

带入该公式，即可证明上述结论。该公式的证明过程如下： alt

\begin{eqnarray} \sum_{i=k}^n\dbinom{i}{k}

当然，如果你是注意力满分的选手，即便也不难注意到这些结论公式。

最后带入这些结论公式即可 AC。

#include <bits/stdc++.h>
using namespace std;

#define debug(x) cerr << #x << ": " << x << '\n';
#define bd cerr << "----------------------" << el;
#define el '\n'
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define lop(i, a, b) for (int i = (a); i < (b); i++)
#define dwn(i, a, b) for (int i = (a); i >= (b); i--)
#define cmax(a, b) a = max(a, b)
#define cmin(a, b) a = min(a, b)
#define x first
#define y second
#define db double

typedef long long LL;
typedef pair<int, int> PII;

constexpr int N = 2e6 + 10, md = 1e9 + 7;
constexpr int INF = 0x3f3f3f3f;

int n, m;
constexpr int P = 998244353;
using i64 = long long;
// assume -P <= x < 2P
int norm(int x) {
    if (x < 0) {
        x += P;
    }
    if (x >= P) {
        x -= P;
    }
    return x;
}
template<class T>
T power(T a, int b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}
struct Z {
    int x;
    Z(int x = 0) : x(norm(x)) {}
    int val() const {
        return x;
    }
    Z operator-() const {
        return Z(norm(P - x));
    }
    Z inv() const {
        assert(x != 0);
        return power(*this, P - 2);
    }
    Z &operator*=(const Z &rhs) {
        x = i64(x) * rhs.x % P;
        return *this;
    }
    Z &operator+=(const Z &rhs) {
        x = norm(x + rhs.x);
        return *this;
    }
    Z &operator-=(const Z &rhs) {
        x = norm(x - rhs.x);
        return *this;
    }
    Z &operator/=(const Z &rhs) {
        return *this *= rhs.inv();
    }
    friend Z operator*(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res *= rhs;
        return res;
    }
    friend Z operator+(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res += rhs;
        return res;
    }
    friend Z operator-(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res -= rhs;
        return res;
    }
    friend Z operator/(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res /= rhs;
        return res;
    }
    friend std::istream &operator>>(std::istream &is, Z &a) {
        i64 v;
        is >> v;
        a = Z(v);
        return is;
    }
    friend std::ostream &operator<<(std::ostream &os, const Z &a) {
        return os << a.val();
    }
};

Z s0 (int k)
{
    return Z(1);
}

Z s1(int k)
{
    return Z(k);
}

Z inv2 = Z(1) / Z(2), inv3 = Z(1) / Z(6), inv4 = Z(1) / Z(24), inv5 = Z(1) / Z(120);

Z s2(int n)
{
    int t = 2;
    n += t - 1;
    Z tmp = Z(n);
    lop(i, 1, t)
        tmp *= Z(n - i);
    tmp *= inv2;
    return tmp;
}

Z s3(int n)
{
    int t = 3;
    n += t - 1;
    Z tmp = Z(n);
    lop(i, 1, t)
        tmp *= Z(n - i);
    tmp *= inv3;
    return tmp;
}

Z s4(int n)
{
    int t = 4;
    n += t - 1;
    Z tmp = Z(n);
    lop(i, 1, t)
        tmp *= Z(n - i);
    tmp *= inv4;
    return tmp;
}


void solve()
{
    Z a, b;
    int k;
    cin >> a >> b >> k;
    Z L1, L2, L3, L4;

    L1 = s1(k) * a;
    L2 = s2(k) * a;
    L3 = s3(k) * a;
    L4 = s4(k) * a;

    L1 += s0(k) * b;
    L2 += s1(k) * b;
    L3 += s2(k) * b;
    L4 += s3(k) * b;
    cout << L1 << ' ' << L2 << ' ' << L3 << ' ' << L4 << el;
}

int main()
{
    // debug(s4(1));
    // debug(s4(2));
    // debug(s4(3));
    cin.tie(0)->sync_with_stdio(false);
    cout.tie(0);
    int T;
    cin >> T;
    while(T --)
    {
        solve();
    }
}

题解 | #S 老师的公式#

A题

B题

C题