//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 的格式要求是 "插入 [该代码片段的中文名]"

{
    "sg函数": {
        "prefix": "acm-7.3sg",
        "body": [
            "#include <bits/stdc++.h>",
            "using namespace std;",
            "",
            "const int N = 1e5 + 5;",
            "int sg[N], f[105], k; // f存允许的步数(需升序), k是步数种类",
            "int vis[N];",
            "",
            "void get_sg(int n) {",
            "\tfor (int i = 1; i <= n; i++) {",
            "\t\t// vis时间戳黑科技：严格O(1)标记，绝对不写 memset",
            "\t\tfor (int j = 1; j <= k && f[j] <= i; j++) {",
            "\t\t\tvis[sg[i - f[j]]] = i;",
            "\t\t}",
            "\t\t// 求 mex",
            "\t\tfor (int j = 0; ; j++) {",
            "\t\t\tif (vis[j] != i) {",
            "\t\t\t\tsg[i] = j;",
            "\t\t\t\tbreak;",
            "\t\t\t}",
            "\t\t}",
            "\t}",
            "}",
            "int main() {",
            "\t// 1. 初始化规则数组 (必须升序!)",
            "\tk = 3;",
            "\tf[1] = 1; ",
            "\tf[2] = 3; ",
            "\tf[3] = 4;",
            "\t// sort(f + 1, f + 1 + k); // 如果题目给的规则没排序，一定要加上这句！",
            "\t",
            "\t// 2. 预处理 SG 函数",
            "\t// 假设题目告诉你，单堆石子最多 10000 个",
            "\tget_sg(10000); ",
            "\t",
            "\t// 3. 处理多堆石子的异或和",
            "\tint m;",
            "\tcin >> m; // m 堆石子",
            "\t",
            "\tint ans = 0;",
            "\tfor (int i = 1; i <= m; i++) {",
            "\t\tint a;",
            "\t\tcin >> a; // 读入这一堆有 a 个石子",
            "\t\t",
            "\t\t// 核心：把这一堆的 sg 值异或进去",
            "\t\tans ^= sg[a]; ",
            "\t}",
            "\t",
            "\t// 4. 审判时刻",
            "\tif (ans != 0) {",
            "\t\tcout << \"先手必胜！\" << endl;",
            "\t} else {",
            "\t\tcout << \"后手必胜！\" << endl;",
            "\t}",
            "\t",
            "\treturn 0;",
            "}"
        ],
        "description": "插入 sg函数"
    }
}