作为教练，在为 N 皇后 II (N-Queens II) 这种计算方案总数的题目设计测试数据时，核心目标是通过数据规模区分选手的算法效率（例如：区分标记数组法和位运算加速法）。

由于本题的输出仅为一个整数，即使 $N$ 很大，输出文件也会非常小（远小于 2MB）。我们的挑战在于生成标准答案的时间效率。

一、 数据生成器 (gen.cpp)

该生成器采用 C++14 标准，内置了位运算优化的求解器。为了防止生成 $N=14, 15$ 等大规模数据时超时，我们利用了位运算的高效性。

#include <iostream>
#include <fstream>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;

// 全局变量用于求解
ll total_ans;
int limit_mask;

/**
 * 使用极致优化的位运算 DFS 求解方案数
 */
void solve(int col, int ld, int rd) {
    if (col == limit_mask) {
        total_ans++;
        return;
    }

    // 取出所有空位
    int pos = limit_mask & (~(col | ld | rd));
    while (pos) {
        // 取出最低位的 1
        int p = pos & -pos;
        pos -= p;
        // 递归下一行：ld 左移, rd 右移
        solve(col | p, (ld | p) << 1, (rd | p) >> 1);
    }
}

int main() {
    // 测试点 n 的规模设计
    // T1-T3: 边界测试 (1, 2, 3)
    // T4: 样例 (4)
    // T5-T7: 中等规模 (5, 6, 8)
    // T8-T10: 压力测试 (10, 12, 13)
    int test_n[] = {1, 2, 3, 4, 5, 6, 8, 10, 12, 13};

    for (int t = 1; t <= 10; ++t) {
        int n = test_n[t - 1];
        
        // 1. 生成输入文件 (.in)
        string in_name = to_string(t) + ".in";
        ofstream fin(in_name);
        fin << n << endl;
        fin.close();

        // 2. 计算标准答案
        total_ans = 0;
        limit_mask = (1 << n) - 1;
        
        // 特殊处理 n=0 或异常情况（虽然本题 n >= 1）
        if (n > 0) {
            solve(0, 0, 0);
        }

        // 3. 生成输出文件 (.out)
        string out_name = to_string(t) + ".out";
        ofstream fout(out_name);
        fout << total_ans << endl;
        fout.close();

        cout << "Generated Case #" << t << ": n = " << n << ", ans = " << total_ans << endl;
    }

    return 0;
}

二、 测试点设计说明 (区分算法复杂度)

三、 数据生成的性能与安全思考

1. 文件大小控制：
   • 本题输出仅为一个整数，10 个测试点的总大小不超过 10KB，完美符合“小于 2MB”的要求。
2. 生成时间优化：
   • 生成器使用了位运算版的 solve 函数。在 $n=13$ 时，方案数为 73712，计算量大约在百万级，即便在普通机器上生成全套数据也仅需不到 0.1 秒。
3. 防止爆栈 (Stack Overflow)：
   • $n=13$ 意味着递归深度仅为 13 层。
   • 每一层递归只使用了 3 个 int 参数和极少量的局部变量。总栈空间消耗约为 $13 \times 64 \text{ bytes} \approx 0.8 \text{ KB}$。
   • 在任何 NOI 评测系统（默认栈空间通常为 8MB 或以上）中，绝对不会爆栈。
4. 异常与边界处理：
   • 除零风险：代码中完全没有除法运算，避开了除零异常。
   • 溢出风险：对于 $n \le 13$，结果都在 int 范围内（$n=13$ 时 $ans=73712$）。但生成器使用了 long long 存储 total_ans，这是竞赛中处理计数类题目的良好习惯，可支持到 $n=20$ 以上（$n=20$ 方案数约为 $3.9 \times 10^{11}$）。
   • 位运算限制：1 << n 在 $n \le 30$ 时都是安全的。

四、 读题理解关键词 (NOI 辅导专版)

作为教练，我要提醒学生在读此类题时，扫描这几个“命门”：

• “总数/个数”：看到它，第一反应是不需要开二维数组存棋盘，省空间。
• “斜线”：立刻在脑中构建位移逻辑（<< 1 和 >> 1）或索引偏移（r+c）。
• “n 范围”：如果 $n > 12$，普通的 bool used[20][20] 暴力检查大概率会 TLE，必须上状态压缩（位运算）。

教练寄语： 同学，这套数据生成器是你检验程序效率的最好工具。如果你的程序在测试点 10 运行超过 1 秒，说明你的回溯常数太大，需要重新审视位运算的威力。加油！

同学，N 皇后问题是回溯算法的“分水岭”。对于求方案总数的问题，我们不需要记录棋盘布局，这给了我们极大的优化空间。

下面我按 NOI 竞赛的训练梯度，为你提供从“基础数组回溯”到“位运算极致优化”的两个版本。

版本一：基础回溯（标记数组法）

这是最适合初学者、逻辑最稳健的版本。通过三个布尔数组，我们实现了 $O(1)$ 时间判断冲突。

思考过程：

• 状态维护：由于每行只能放一个，我们按“行”递归。
• 冲突检查：
  • 列冲突：cols[c]
  • 主对角线（左上到右下）：row - col 是定值。偏移处理：diag1[row - col + n]。
  • 副对角线（右上到左下）：row + col 是定值。diag2[row + col]。
• 复杂度：时间 $O(N!)$，空间 $O(N)$。

#include <iostream>
#include <vector>

using namespace std;

int n, ans = 0;
// 使用 bool 数组记录列、主对角线、副对角线的占用情况
bool cols[20], d1[40], d2[40];

void dfs(int r) {
    if (r == n) {
        ans++; // 搜到底部，方案数加 1
        return;
    }

    for (int c = 0; c < n; c++) {
        // 关键点：主对角线索引为 r-c+n (加n防止负数)，副对角线为 r+c
        if (!cols[c] && !d1[r - c + n] && !d2[r + c]) {
            // 标记现场
            cols[c] = d1[r - c + n] = d2[r + c] = true;
            
            dfs(r + 1);
            
            // 回溯：恢复现场（易错点：标记必须重置为 false）
            cols[c] = d1[r - c + n] = d2[r + c] = false;
        }
    }
}

int main() {
    // NOI 竞赛标准：优化输入输出效率
    ios::sync_with_stdio(false);
    cin.tie(0);

    if (!(cin >> n)) return 0;
    
    dfs(0);
    cout << ans << endl;

    return 0;
}

版本二：最优复杂度（位运算状态压缩版）

在 NOI 竞赛中，如果 $n$ 达到 13~15，数组访问的常数开销会非常明显。位运算版本是竞赛选手的标配。

思考过程：

• 核心逻辑：用三个整数的二进制位表示占用状态。
• 位移奥秘：
  • col: 垂直向下，位不移动。
  • ld (左斜线): 随行向下，每层向左移动 1 位。
  • rd (右斜线): 随行向下，每层向右移动 1 位。
• 取出可用位：pos = mask & ~(col | ld | rd)。
• 复杂度：时间 $O(N!)$，空间 $O(N)$。由于省去了数组寻址，常数极小。

#include <iostream>

using namespace std;

int n, total_mask, ans = 0;

/**
 * @param col 当前所有列的占用情况
 * @param ld  当前所有左斜线的占用情况
 * @param rd  当前所有右斜线的占用情况
 */
void dfs(int col, int ld, int rd) {
    if (col == total_mask) {
        ans++;
        return;
    }

    // 取出当前行所有可放皇后的位置（位为 1 表示可用）
    // ~(col | ld | rd) 会把高位的 0 变 1，所以必须 & total_mask 截断
    int pos = total_mask & ~(col | ld | rd);

    while (pos) {
        // 关键技巧：p = pos & -pos 得到最右边的 1 (Lowbit)
        int p = pos & -pos;
        
        // 放置皇后：更新 col, ld, rd，递归进入下一层
        // ld | p 之后左移，rd | p 之后右移，完美模拟斜线发散
        dfs(col | p, (ld | p) << 1, (rd | p) >> 1);
        
        // 关键技巧：pos &= (pos - 1) 将最右边的 1 删掉，尝试下一个位置
        pos &= (pos - 1); 
        // 注意：位运算版不需要显式“回溯”标记，因为状态是通过参数传递的
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);

    if (!(cin >> n)) return 0;

    // 构造一个 n 位的全 1 掩码。例如 n=4, total_mask = 1111 (二进制)
    total_mask = (1 << n) - 1;

    dfs(0, 0, 0);
    cout << ans << endl;

    return 0;
}

复杂度分析思考过程

1. 时间复杂度分析：

   • 无论是哪种实现，本质都是深度优先遍历一颗高度为 $n$ 的搜索树。
   • 第一行有 $n$ 个位置可选，第二行最多 $n-2$ 个，以此类推。
   • 理论上复杂度为 $O(n!)$。虽然 $n=15$ 时 $15!$ 非常大，但因为斜线约束极强，大量分支被提前剪掉，位运算版在 1 秒内跑完 $n=15$ 是完全可能的。

2. 空间复杂度分析：

   • 主要开销是递归调用的系统栈，深度为 $O(n)$。
   • 位运算版几乎不消耗额外辅助数组，内存占用极低（$O(n)$）。

时间复杂度优化建议

1. 利用对称性：
   • N 皇后棋盘是左右对称的。你可以只搜索第一行的前一半位置，然后将结果乘以 2。
   • 如果 $n$ 是奇数，第一行中间的位置单独搜一次。这可以直接减少 50% 的计算量。
2. 内联与寄存器：
   • 在极其严苛的题目中，可以给 dfs 函数加 inline 关键字，或者利用 register（虽然 C++14 已弃用，但部分竞赛编译器仍有优化效果）来处理频繁变化的变量。

读题关键词总结 (NOI 考场必看)

1. “彼此不能相互攻击”：核心约束，要求行、列、两条斜线都唯一。
2. “方案个数”：这在暗示你：不要浪费空间去存棋盘，直接用标记或位运算。
3. “斜线”：在草稿纸上立刻写下 r+c 和 r-c。
4. $n$ 的范围：
   • $n \le 10$：普通回溯随便写。
   • $10 < n \le 15$：必须用位运算和高效剪枝。
   • $n > 15$：可能需要更高级的启发式搜索（如禁忌搜索）或数学构造法。

教练寄语： 位运算版本的 N 皇后是搜索算法常数优化的经典案例。当你能熟练手写出 pos & -pos 和 pos & (pos - 1) 时，你已经掌握了状态压缩搜索的灵魂。加油！