Omkar and Duck

Mier_Samuelle · 2026-07-21 16:05:00 · 题解

可以发现，一条从左上角到右下角的路径，一定经过了每条副对角线恰好一次。一个自然的想法是，将每条副对角线视作一个数位，给该条对角线上的每个格子赋上不同的权值，直接把路径上经过的所有格子的权值拼成一个整数。

然而这样肯定塞不进 10^{16}。注意到 2^{50} \le 10^{16}，于是往二进制的方向想。假设我们已经确定了一条路径的一部分，现在位于 (i,j)，那我们其实只有 (i+1,j),(i,j+1) 两个格子可以走，把这两个格子区分开即可，即一个赋 2^{i+j+1}，一个赋 0。

以样例为例，对于 n=4，构造以下矩阵：

对于第一组询问，给定 k=39=(0100111)_2。这个二进制表示中的每一位就恰好对应了我们走的每一步，根据当前 i 的奇偶性移动到对应的格子即可。

:::success[Code]{open}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[30][30];
signed main(){
    int n, q;
    cin >> n;
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            if (i & 1){
                a[i][j] = 0;
            }
            else{
                a[i][j] = 1ll << (i + j);
            }
            cout << a[i][j] << " ";
        }
        cout << endl;
    }
    cin >> q;
    while (q--){
        ll k;
        cin >> k;
        int x = 0, y = 0;
        for (int i = 1; i < 2 * n; i++){
            cout << x + 1 << " " << y + 1 << endl;
            if (k >> i & 1){
                if (x & 1){
                    x++;
                }
                else{
                    y++;
                }
            }
            else{
                if (x & 1){
                    y++;
                }
                else{
                    x++;
                }
            }
        }
    }
    return 0;
}

:::