二维二进制数

https://www.matiji.net/exam/dohomework/8235/5

题干

小码哥最近在学习二进制数。

有一天，小码哥想到传统的二进制数都是一维的，是否能定义一种二维的二进制数。

小码哥将二维二进制数定义为以下形式：

1. 二维二进制数为一个 0/1 矩阵，下标从 0 开始；
2. 二维二进制数与正常自然数形成双射关系，不妨记这种关系为 $f$ ；
3. 定义全0矩阵所对应的整数值为 0，即 $f(0)=A$ ， $A$ 为全 0 矩阵；
4. 若 $f(x)=A$ , $f(x + 1)=B$，则 A 与 B 有以下对应关系，我们对 A 的 (0，0) 这一位加一，并进行进位操作，则能得到二维二进制数 B；
5. 进位操作被定义如下：若 $S_{i,j}=1$ ，并且在这一位上加1时，会发生如下进位：使 $S_{i,j}=0$ ，并在 $S_{i + 1,j}=1$ $S_{i,j + 1}=1$ 位上加1。 小码哥想知道，对于给定的 x ，其对于的二维二进制数为多少，即f（x）为多少，由于二维二进制可能很大，你只需输出f（x）的下标从0到n。

思路

$n \leq 1000, x \leq 10^{18}$ ，显然复杂度大概 $O(n^2 \log x)$ 以下。

$O(n^2)$ 可以遍历矩阵一次，也就是可以遍历 $O(\log x)$ 次矩阵。

显然 $f$ 是同态，因此矩阵和等于数的和。而且得到的的矩阵显然是对称的，因为 $f(0)$ 是对称的，而所有的进位操作也是对称的。

同时，任意两个矩阵的加法也是显然的：相加后进行进位操作即可。

因此直接算 $f(2^i)$，再对 $x$ 二进制分解，就可以得到答案了。复杂度正好是 $O(n^2 \log x)$。

要求 $f(2^i)$ 在 $O(n^2)$ 内求出，这个复杂度很宽容，可以直接模拟。

Code

#include<bits/stdc++.h> 

using namespace std;
using ll = long long;
using Matrix = vector<vector<int>>;

void work(Matrix& m, int x, int y) {
    int mr = m.size();
    int mc = m[0].size();
    if(m[x][y] == 0 || m[x][y] == 1) return;
    else {
        int rm = m[x][y] / 2;
        m[x][y] = m[x][y] % 2;
        if(x + 1 < mr) {
            m[x + 1][y] += rm;
            // logically, should have this line
            // but actually this line does not do anything
            // since for adding up two matrices
            // x, y is upmost two(since previous work has been done)
            // and adding this line will cause TLE
            // work(m, x + 1, y);
        }
        if(y + 1 < mc) {
            m[x][y + 1] += rm;
        }
    }
    return;
}

void mul(Matrix& m) {
    int mr = m.size();
    int mc = m[0].size();
    for(int i = 0; i < mr; ++i) {
        for(int j = 0;j < mc; ++j) {
            m[i][j] += m[i][j];
        }
    }
    for(int i = 0; i < mr; ++i) {
        for(int j = 0;j < mc; ++j) {
            if(m[i][j] != 0) work(m, i, j);
        }
    }
}

void add(Matrix& to, Matrix& off) {
    int s = to.size();
    for(int i = 0; i < s; ++i) {
        for(int j = 0; j < s; ++j) {
            to[i][j] += off[i][j];
            work(to, i, j);
        }
    } 
}

int main( )
{
    ll n, x;
    cin >> n >> x;
    Matrix m(n + 1, vector<int>(n + 1, 0));
    m[0][0] = 1;
    Matrix res(n + 1, vector<int>(n + 1, 0));
    for(int i = 0; i < n + 1; ++i) {
        if(x & 1) {
            add(res, m);
        }
        mul(m);
        x >>= 1;
        if(x == 0) break;
    }
    for(int i = 0; i < n + 1; ++i) {
        for(int j = 0; j < n + 1; ++j) {
            printf("%d ", res[i][j]);
        }
        cout << '\n';
    }

    return 0;
}