# C

# 题目大意

给定一个数列 $A=(a_1, ..., a_n)$
求 $\sum_{i \le i < j \le N} (a_i·a_j)$

# 数据范围

$2 \le N \le 3 \times 10^5$
$1 \le A_i \le 10^4$

# 题解

考前缀和，求 $\sum\limits_{i=1}^{n}(a_i \times \sum\limits_{j=i+1}^{n}a_j)$

c++

int n;

void solve () {
    cin >> n;
    vector<int> a(n + 1), pre(n + 1);

    for (int i = 1; i <= n; i++)
        cin >> a[i], pre[i] = pre[i - 1] + a[i];
    
    int res = 0;
    for (int i = 1; i <= n; i++)
        res += a[i] * (pre[n] - pre[i]);

    cout << res << '\n';
}

# D

# 题目大意

给你一个 $H$ 行 $W$ 列的网格 $S$ ，其中 . 表示空白地面， # 表示墙， E 表示安全出口，你要把每个 . 变成 ^ v < > 的其中一个，要求每个 . 到 E 的路径都是最短的

# 数据范围

$1 \le H, W \le 1000$
确保每个 . 一定能抵达 E

# 题解

题目要求的是，对于每个 . ，其要变成 > < ^ V ，沿着路径能走到 E ，并且距离最短，显然用 $BFS$ ，一开始把所有 E 的坐标都 $push$ 进队列，然后不断迭代

c++

int dx[] = {0, 0, 0, 1, -1, 1, 1, -1, -1};  // 行
int dy[] = {0, 1, -1, 0, 0, 1, -1, 1, -1};  // 列

int n, m;
vector<vector<char>> a, res;
vector<vector<bool>> st;

char dir[] = {'z', '<', '>', '^', 'v'};

bool check(int x, int y) {
    return (x >= 1 && x <= n && y >= 1 && y <= m);
}

void solve () {
    cin >> n >> m;

    st = vector<vector<bool>>(n + 1, vector<bool>(m + 1, false));
    a = vector<vector<char>>(n + 1, vector<char>(m + 1));
    res = vector<vector<char>>(n + 1, vector<char>(m + 1));

    queue<PII> q;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
                
            if (a[i][j] == 'E')
                q.push({i, j});
            
            if (a[i][j] != '.')
                res[i][j] = a[i][j];
        }
    
    while (q.size()) {
        auto [x, y] = q.front();
        q.pop();

        for (int i = 1; i <= 4; i++) {
            int xx = x + dx[i], yy = y + dy[i];
            
            if (check(xx, yy)) {
                if (st[xx][yy] || a[xx][yy] != '.')
                    continue;

                st[xx][yy] = true, res[xx][yy] = dir[i], q.push({xx, yy});
            }
        }
    }

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cout << res[i][j] << (j == m ? "\n" : "");
}

# E

# 题目大意

你有 $A$ 个苹果， $B$ 个橙子， $C$ 串香蕉， $D$ 串葡萄
求把他们从左往右排成一排的方案数，要求

所有的苹果都在所有的香蕉的左边
所有的苹果都在所有的葡萄的左边
所有的橙子都在所有的葡萄的左边

求一共有多少种排列方式，答案对 $998244353$ 取模

# 数据范围

$1 \le A,B,C,D \le 10^6$

# 题解

显然，题目的排列应该是这样的

data

|----苹果----|
|---------橙子---------|
             |-----------香蕉-------------|
                   x        c - x
                       |-------葡萄-------|

我们可以发现，香蕉在葡萄最左端分界线的左右两端的个数，会影响最终答案，不放假设左端有

x

个，则有

左侧是在 $A$ $A$ 个苹果， $x$ $x$ 个香蕉之间，插入 $B$ $B$ 个橙子
- 苹果必须在香蕉前面，所以 苹果 - 香蕉 ，一共有 $A+x$ 个，即 $A+x+1$ 个有顺序的空，插 $B$ 个无顺序的球
- 把 $B$ 个无顺序的球分成 $A+x+1$ 个部分，答案是 C_{B+A+x+1-1}^{A+x+1-1}=C_{B+A+x}^
右侧是在 $D-1$ $D - 1$ 个葡萄中，插入 $c-x$ $c - x$ 个香蕉
- 为什么是 $D-1$ 个葡萄？因为香蕉是以最左侧的第一个葡萄为分界的，所以右侧的左边第一个必须是葡萄
- 也就是，一共有 $D$ 个有顺序的空，插入 $c-x$ 个香蕉
- 把 $C-x$ 个球，分为 $D$ 个部分，答案是 C_{C-x+D-1}^

这种理解成放球问题会有点绕，不妨这样理解

最终目的是实现 $x$ 个 $A$ 物品和 $y$ 个 $B$ 物品混合放的最终方案数，那不就是， $x+y$ 个位置，任选 $x$ 或 $y$ 吗，也就是 $C_{x+y}^x$
对照到上面两侧
左侧是 $A+x$ 和 $B$ 的排列，也就是 C_{A+x+B}^
右侧是 $D-1$ 和 $C-x$ 的排列，也就是 C_{D-1+C-x}^

C++

vector<int> fac(N), inv(N);

int qmi(int a, int b) {
    int res = 1;
    
    while (b) {
        if (b & 1)
            res = res * a % MOD;
        a = a * a % MOD, b >>= 1;
    }

    return res;
}

int cal(int n, int m) {
    if (m < 0 || m > n)
        return 0;
    return fac[n] * inv[m] % MOD * inv[n - m] % MOD;
}

int a, b, c, d;

void solve () {
    fac[0] = 1;
    for (int i = 1; i < N; i++)
        fac[i] = fac[i - 1] * i % MOD;
    inv[N - 1] = qmi(fac[N - 1], MOD - 2);
    for (int i = N - 2; i >= 0; i--)
        inv[i] = inv[i + 1] * (i + 1) % MOD;
    
        cin >> a >> b >> c >> d;

    if (d == 0) {
        cout << cal(a + b + c, b) << '\n';
        return;
    }

    int res = 0;
    for (int x = 0; x <= c; x++) {
        int t1 = cal(a + b + x, a + x), t2 = cal(c - x + d - 1, d - 1);
        res = (res + t1 * t2 % MOD) % MOD;
    }

    cout << res << '\n';
}

# C

# 题目大意

# 数据范围

# 题解

# D

# 题目大意

# 数据范围

# 题解

# E

# 题目大意

# 数据范围

# 题解

计算机视觉

组合数-放球问题