题解：CF1392E Omkar and Duck

ssy666666 · 2026-07-21 15:37:17 · 题解

首先，这种题有一种标准的处理逻辑，即通过拆位，通过每一位的值代表多种状态（一般为两种）。

先把最大值小于 10^{16} 弱化掉，看看这个问题有没有什么好的方法。

这个很好办，我们给格点 (i,j) 赋一个 2^{i(n-1)+j} 的权值，那么和的每一位就可以直接代表有没有经过这一个点，我们需要的权值最大为 2^{50^2}。

但是，考虑到 n^2 个格点我们无法经过每一个，具体的，我们只会经过 2n-1 个，那么，我们考虑，有没有方法，能不能就这 2n-1 个点进行刻画？

对这 2n-1 个点进行刻画实则等价于对每一条边进行刻画，边的条数为 2n-2 条，并且每到一个点，我们只有两种选择——向右或向下。这刚好和我们拆位的逻辑相似，并且 \log_2 10^{16} \approx 53，也支持了我们的做法。现在的问题就变为了：如何区分向下走和向右走？

没啥思路，那让我们把图画出来看看：

我们这里把向下改为向上，实际上是等价的。此后，提到的“向上”也都代表题意中的“向下”

我们分别考虑每一步可能到达的点：

实际上，我们要区分的就是蓝线上相邻的两个点。并且不能和先前的值冲突。因此，我们考虑通过二进制一位的“0”和“1”来区分向右走和向上走。

并且，我们发现，对于一条蓝线上的点，他们之间只需要相邻的两个点值不同，不相邻的点值相同没有影响。因为我们已经得到了当前位置，要推现在要向上还是向右，实际上只关注相邻点。因此，我们可以有如下构造：

对于点 (x,y)，若 x \equiv 1 \pmod{n}，我们将它的值设定为 2^{x + y -2}，反之设定为 0。

AC Code

#include<bits/stdc++.h>
#define int long long
using namespace std ;
const int MAXN = 30 ;
int pow2[MAXN] ;

signed main() {
    ios::sync_with_stdio(0) ;
    cin.tie(0) ;
    cout.tie(0) ;

    int n ;
    cin >> n ;

    pow2[0] = 1 ;
    for (int i = 1 ; i <= 2 * n ; i ++) {
        pow2[i] = pow2[i - 1] * 2 ;
    }

    for (int i = 1 ; i <= n ; i ++) {
        for (int j = 1 ; j <= n ; j ++) {
            if (i % 2 == 1) {
                cout << pow2[i + j - 2] << " " ;
            }
            else {
                cout << 0 << " " ;
            }
        }
        cout << endl ;
    }

    int q ;
    cin >> q ;
    while (q--) {
        int cnt ;
        cin >> cnt ;

        int nowx = 1 , nowy = 1 ;
        cout << 1 << " " << 1 << endl ;
        for (int i = 1 ; i < 2 * n - 1 ; i ++) {
            int p = cnt & (1ll << i) ;
            int g = (nowx & 1) ^ (p != 0) ;
            if (g == 0) {
                nowy ++ ;
            }
            else {
                nowx ++ ;
            }
            cout << nowx << " " << nowy << endl ;
        }
    }

    return 0 ;
}