ABC458

A

字符串简单应用, 使用 substr 或者其他语言的切片类似的东西

s = input().strip()
n = int(input())
print(s[n: len(s) - n])

B

暴力模拟

auto solve() {
    int h, w;
    std::cin >> h >> w;

    for (int hi = 0; hi < h; ++hi) {
        for (int wi = 0; wi < w; ++wi) {
            int ans = (
                (hi == 0 ? 0 : 1) + 
                (hi == h - 1 ? 0 : 1) + 
                (wi == 0 ? 0 : 1) + 
                (wi == w - 1 ? 0 : 1)
            );
            std::cout << ans << " ";
        }
        std::cout << "\n";
    }
}

C

计算每个点作为答案的时候产生的贡献

auto solve() {
    std::string s;
    std::cin >> s;

    using i64 = long long;
    i64 ans = 0;

    for (int i = 0; i < s.size(); ++i) {
        if (s[i] != 'C') continue;
        ans += 1 + std::min<i64>(s.size() - 1 - i, i);
    }

    std::cout << ans << "\n";
}

D

对顶堆板子

#include <bits/stdc++.h>

auto solve() {
    int x;
    std::cin >> x;

    /*
        使用对顶堆, 维护 ans  
        两个堆, 大于 ans 的最小值 和 小于 ans 的最大值  
        分类放置, 然后根据两个堆的大小来弹出推入更改 ans
    */

    int ans = x;
    std::priority_queue<int> les;
    std::priority_queue<int, std::vector<int>, std::greater<>> grt;

    int q;
    std::cin >> q;

    for (int _ = 0; _ < q; ++_) {
        int a, b;
        std::cin >> a >> b;

        if (a >= ans) grt.emplace(a);
        else les.emplace(a);

        if (b >= ans) grt.emplace(b);
        else les.emplace(b);

        if (grt.size() > les.size()) {
            les.emplace(ans);
            ans = grt.top();
            grt.pop();
        }
        else if (grt.size() < les.size()) {
            grt.emplace(ans);
            ans = les.top();
            les.pop();
        }

        std::cout << ans << "\n";
    }
}

E

给定数量的三元素排列, 求 1, 3 不能相邻的不同排列个数
插板法, 先固定 2 的位置, 留出 $x_2 + 1$ 个间隔, 每个间隔要不只能放 1, 要不只能放 3
假设 $i$ 个空位放 1 且放满, 剩下 $x_2 + 1 - i$ 个空位放 3 且不要求所有空位都有 3
那么遍历所有的 $i$ 并求和可求得所有情况

WIDA 板子里面抄了点结论

球盒模型

参考链接。给定 $n$ 个小球 $m$ 个盒子。

球同，盒不同、不能空

隔板法： $N$ 个小球即一共 $N-1$ 个空，分成 $M$ 堆即 $M-1$ 个隔板，答案为 $\dbinom{n-1}{m-1}$ 。

球同，盒不同、能空

隔板法：多出 $M-1$ 个虚空球，答案为 $\dbinom{m-1+n}{n}$ 。

球同，盒同、能空

$\dfrac{1}{(1-x)(1-x^2)\dots(1-x^m)}$ 的 $x^n$ 项的系数。动态规划，答案为
$dp[i][j]= \left\{\begin{matrix} dp[i][j-1]+dp[i-j][j] & i\geq j \\ dp[i][j-1] & i \lt j \\ 1 & j==1 \ || \ i \leq 1 \end{matrix}\right.$

球同，盒同、不能空

$\dfrac{x^m}{(1-x)(1-x^2)\dots(1-x^m)}$ 的 $x^n$ 项的系数。动态规划，答案为
$dp[n][m]= \left\{\begin{matrix} dp[n-m][m] & n\ge m \\ 0 & n \lt m \\ \end{matrix}\right.$

球不同，盒同、不能空

第二类斯特林数 ${\tt Stirling2}(n,m)$ ，答案为
$dp[n][m]= \left\{\begin{matrix} m*dp[n-1][m]+dp[n-1][m-1] & 1 \le m \lt n\\ 1 & 0 \le n == m\\ 0 & m == 0 且 1 \le n \end{matrix}\right.$

球不同，盒同、能空

第二类斯特林数之和 $\displaystyle\sum_{i=1}^m{\tt Stirling2}(n,m)$ ，答案为 $\sum_{i = 0}^{m} dp[n][i]$ 。

球不同，盒不同、不能空

第二类斯特林数乘上 $m$ 的阶乘 $m!\cdot{\tt Stirling2}(n,m)$ ，答案为 $dp[n][m] * m!$ 。

球不同，盒不同、能空

答案为 $m^n$ 。

i64 mypow(i64 n, i64 k) { // 复杂度是 log N
    i64 r = 1;
    for (; k; k >>= 1, n *= n) {
        if (k & 1) r *= n;
    }
    return r;
}
 
vector<vector<i64>> comb;
void YangHuiTriangle(int n = 60) {
    comb.resize(n + 1, vector<i64>(n + 1));
    comb[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        comb[i][0] = 1;
        for (int j = 1; j <= n; j++) {
            comb[i][j] = comb[i - 1][j] + comb[i - 1][j - 1];
        }
    }
}
 
vector<vector<i64>> S;
void Stirling2(int n = 15) {
    S.resize(n + 1, vector<i64>(n + 1));
    S[1][1] = 1;
    for (int i = 2; i <= 15; i++) {
        for (int j = 1; j <= i; j++) {
            S[i][j] = S[i - 1][j - 1] + S[i - 1][j] * j;
        }
    }
}
 
vector<vector<i64>> dp;
void GeneratingFunction(int n = 15) {
    dp.resize(n + 1, vector<i64>(n + 1));
    for (int i = 0; i <= n; i++) {
        dp[i][1] = 1;
        for (int j = 2; j <= n; j++) {
            dp[i][j] = dp[i][j - 1];
            if (i >= j) dp[i][j] += dp[i - j][j];
        }
    }
}
 
vector<i64> fac;
void Fac(int n = 30) {
    fac.resize(n + 1);
    fac[0] = 1;
    for (int i = 1; i <= n; i++) {
        fac[i] = fac[i - 1] * i;
    }
}
 
i64 A(int n, int m) {
    if (n < 0 || m < 0 || n < m) return 0;
    return fac[n] / fac[n - m];
}
 
i64 C(int n, int m) {
    if (n < 0 || m < 0 || n < m) return 0;
    return comb[n][m];
}
 
signed main() {
    int Task = 1;
    for (cin >> Task; Task; Task--) {
        int op, n, m;
        cin >> op >> n >> m;
 
        i64 ans = -1;
        if (op == 1) { // 球同，盒同、能空
            ans = dp[n][m];
        } else if (op == 2) { // 球同，盒同、至多放一个
            ans = (n <= m);
        } else if (op == 3) { // 球同，盒同、至少放一个
            ans = (n < m ? 0 : dp[n - m][m]);
        } else if (op == 4) { // 球同，盒不同、能空
            ans = C(m - 1 + n, n);
        } else if (op == 5) { // 球同，盒不同、至多放一个
            ans = C(m, n);
        } else if (op == 6) { // 球同，盒不同、至少放一个
            ans = C(n - 1, m - 1);
        } else if (op == 7) { // 球不同，盒同、能空
            ans = accumulate(S[n].begin() + 1, S[n].begin() + m + 1, 0LL);
        } else if (op == 8) { // 球不同，盒同、至多放一个
            ans = (n <= m);
        } else if (op == 9) { // 球不同，盒同、至少放一个
            ans = S[n][m];
        } else if (op == 10) { // 球不同，盒不同、能空
            ans = mypow(m, n);
        } else if (op == 11) { // 球不同，盒不同、至多放一个
            ans = A(m, n);
        } else if (op == 12) { // 球不同，盒不同、至少放一个
            ans = fac[m] * S[n][m];
        }
        cout << ans << "\n";
    }
}

达 1e6 的组合数

利用组合数公式 $\dbinom{n}{m} = \frac{n!}{n!(n-m)!}$ 计算
使用公式 $fac_{i+1} = fac_{i} * (i + 1)$ 计算阶乘
两边同时取倒数, 移项, 得到 $inv_{i+1} * (i + 1) = inv_{i}$
可以利用快速幂求得 $fac_{MAXVAL}$ 的逆元之后从高到低线性递推

constexpr int MOD = 998244353;
constexpr int MAXVAL = 3'000'005;

template<const int p = MOD> 
auto fpow(i64 a, i64 b) {
    i64 res = 1 % p;
    for (; b; b >>= 1, a = a * a % p) {
        if (b & 1) res = res * a % p;
    }
    return res;
}

int fac[MAXVAL], inv[MAXVAL];
auto precalc() {
    fac[0] = 1;
    for (int i = 1; i < MAXVAL; ++i) {
        fac[i] = (i64)fac[i - 1] * i % MOD;
    }
    inv[MAXVAL - 1] = fpow(fac[MAXVAL - 1], MOD - 2);
    for (int i = MAXVAL - 2; i >= 0; --i) {
        inv[i] = (i64)inv[i + 1] * (i + 1) % MOD;
    }
}

auto C(int n, int r) {
    if (r < 0 || r > n) return i64{};
    return (i64)fac[n] * inv[r] % MOD * inv[n - r] % MOD;
}

auto solve() {
    int a, b, c;
    std::cin >> a >> b >> c;

    int ans = 0;
    for (int i = 1; i <= std::min(a, b + 1); ++i) {
        ans = (ans + 
            (i64)C(b + 1, i) % MOD * 
            C(a - 1, i - 1) % MOD * 
            C(c + b - i, b - i) % MOD
        ) % MOD;
    }
    
    std::cout << ans << "\n";
}

常规线性递推逆元

假设大质数模数是 $p$ , 目标是求 $i$ 在模 $p$ 意义下的逆元
$p = ki + r$ , $k = \lfloor p / i \rfloor$ , $r \equiv p \pmod i$
$0 = ki + r \pmod p$
两边同时乘 $i^{-1} r^{-1}$ 变成 $0 = kr^{-1} + i^{-1}$
所以 $i^{-1} = -kr^{-1}$
已知 $r < i$ , 故可以使用线性递推从小到大求 $i^{-1}$
公式为 inv[i] = (p - p / i) * inv[p % i] % p

F

据说是 AC 自动机上 dp, 不会

G

据说是斜率优化 dp, 不会