//Place your snippets for cpp here. Each snippet is defined under a snippet name and has a prefix, body and 
// description. The prefix is what is used to trigger the snippet and the body will be expanded and inserted. Possible variables are:
// $1, $2 for tab stops, $0 for the final cursor position, and ${1:label}, ${2:another} for placeholders. Placeholders with the 
// same ids are connected.
// prefix 的格式要求是 acm-[一级标题编号].[二级标题编号][该代码片段的英文简称]
// description 的格式要求是 "插入 [该代码片段的中文名]"

{
    "前缀基": {
        "prefix": "acm-7.6b",
        "body": [
            "#include <iostream>",
            "#include <vector>",
            "",
            "using ll = long long;",
            "using namespace std;",
            "const int MOD = 998244353;",
            "",
            "ll qpow(ll a, ll b) {",
            "    ll res = 1;",
            "    a %= MOD;",
            "    while (b) {",
            "        if (b & 1) res = res * a % MOD;",
            "        a = a * a % MOD;",
            "        b >>= 1;",
            "    }",
            "    return res;",
            "}",
            "",
            "/**",
            " * 线性批量求逆元 (前缀积法)",
            " * 传入需要求逆元的数组 a (1-indexed)，将结果存入 inv_a (1-indexed)",
            " * 时间复杂度: O(n + log(MOD))",
            " */",
            "void linear_inv(const std::vector<ll>& a, std::vector<ll>& inv_a) {",
            "    int n = a.size() - 1;",
            "    if (n <= 0) return;",
            "    std::vector<ll> pre(n + 1, 1), inv_pre(n + 1, 1);",
            "    for (int i = 1; i <= n; i++) {",
            "        pre[i] = pre[i - 1] * a[i] % MOD;",
            "    }",
            "    inv_pre[n] = qpow(pre[n], MOD - 2);",
            "    for (int i = n; i >= 1; i--) {",
            "        inv_pre[i - 1] = inv_pre[i] * a[i] % MOD;",
            "    }",
            "    for (int i = 1; i <= n; i++) {",
            "        inv_a[i] = inv_pre[i] * pre[i - 1] % MOD;",
            "    }",
            "}"
        ],
        "description": "插入 前缀基"
    }
}