Walk on Matrix

Walk on Matrix

Walk on Matrix 题目链接

思路

我们先想一下有没有可能存在一种特殊情况，用题目的algorithm算的的结果是0，而我们的正确答案是k。

于是我们有了如下构造

其中A的各个位上都是1，(B = ar{A} + ar{K})，也就是异或，这里的加号是逻辑上的或，(C = K)

所以有两条路到D

• (A->B->D)，其值为(A(ar {A} + ar {K})D = ar {K}D)
• (A->C->D)，其值为(AKD = KD)

要使其中的一个为零一个为K，则(D = ar {K})

我们考虑走到B时，(B =A(ar {A} + ar {K}))，走到C时，(C = K)，接下来我们考虑如何变化能使B > C

我们对B,C同时与上一个A得到(B =ar {A} + ar {K}, C = K)，我们知道K是小于1e5的所以k最高位是16位，而A的有17位，我们明显得到(B =ar {A} + ar {K} > C = K)

于是我们有了一个2 * 3的特殊矩阵。

(A, ar{A} + ar {K}, A)

(K, A, K)

代码

这道题目真是构造了一个多小时啊。

#include<bits/stdc++.h>
using namespace std;
int main() {
    int k;
    cin >> k;
    cout << 2 << " " << 3 << "
";
    cout << ((1 << 18) - 1) << " " << (((1 << 18) - 1) ^ k) << " " << ((1 << 18) - 1) << "
";
    cout << k << " " << ((1 << 18) - 1) << " " << k << "
";
    return 0 ;
}