combinatorics - 计算可能的 "snake"密码

Question

我们都知道移动设备上的新密码屏幕。它由要连接的点矩阵组成。

唯一密码是积分的向量。这些点可以通过以下限制与自己连接:

一个点只能连接到另外一个点

如果目标点和自由点在同一条线上，则将强制一条线连接到更近的点。例如:

由于之前未连接中间点，因此无法将顶部连接到底部。

第一个限制条件是查找树的数量。这是我找不到计算方法的第二个限制。

有没有一种更简单的方法来计算可能性的数量，或者唯一的方法就是生成所有可能性并对它们进行计数？

Answer 1

由于在无向图中对simple paths进行计数的一般问题是#P-complete，并且正如注释中所指出的那样，推测对self-avoiding paths in a grid进行计数的类似问题也很难，因此，我认为考虑如何解决该问题是适当的。 o((n * n)!)时间(在您的情况下，n = 3)。

我们必须牢记通常适用于“真实”智能手机的其他特殊情况:

如果已经访问过中间节点，我们可以遍历这些中间节点。例如通常可以去(0,0)->(1,1)->(0,2)->(2,0)

有一种简单的动态编程方法，至少应能够解决5x5的情况:设f(i，j，visited)为当前位于顶点(i，j)时的方式数，而 visited为我们之前访问的节点集。通过尝试所有可能的移动并递归，我们可以使用动态编程来计算f。我们可以将 visited表示为位掩码。这样，可能性的总数将为 sum(i,j, f(i,j, {(i,j)}))。

结果如下:

n = 2     64
n = 3     389497
n = 4     4350069824956
n = 5     236058362078882840752465

从信息理论的角度来看，即使对于n = 4，也似乎非常安全。

下面是我使用的C++实现。由于结果可能非常大，因此程序会以一些大素数为模来计算结果，以便我们可以使用中国余数定理来重构解。

#include <bits/stdc++.h>
#include <cassert>
using namespace std;

typedef long long ll;

const int n = 5;
bool getbit(int visited, int i, int j) { return visited & (1<<(i*n + j)); }
int setbit(int visited, int i, int j) { return visited | (1<<(i*n + j)); }
bool inrange(int i) { return 0 <= i && i < n; }
short dp[n][n][1<<(n*n)];
int mod;
int f(int i, int j, int visited) {
    short& res = dp[i][j][visited];
    if (res != -1) return res;
    res = 1;
    for (int di = -i; di <= n-i-1; ++di)
        for (int dj = -j; dj <= n-j-1; ++dj) {
            if ((di == 0 && dj == 0) || abs(__gcd(di, dj)) != 1) continue;
            int i2 = i + di, j2 = j + dj;
            while (inrange(i2) && inrange(j2) && getbit(visited, i2, j2)) {
                i2 += di;
                j2 += dj;
            }
            if (inrange(i2) && inrange(j2)) {
                res += f(i2, j2, setbit(visited, i2, j2));
                if (res >= mod) res -= mod;
            }
        }
    return res;
}

int primes[] = {
    15013,
    15017,
    15031,
    15053,
    15061,
    15073,
    15077,
    15083,
    15091,
    15101,
};

int main(int argc, char **argv) {
    int lo = 0;
    int hi = sizeof primes / sizeof *primes - 1;
    if (argc > 1) {
        stringstream ss; ss << argv[1]; ss >> lo;
        hi = lo;
    }
    for (int p = lo; p <= hi; ++p) {
        mod = primes[p];
        cout << mod << " " << flush;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                for (ll m = 0; m < (1<<(n*n)); ++m)
                    dp[i][j][m] = -1;
        ll answer = 0;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                answer = (answer + f(i, j, setbit(0, i, j))) % mod;
        cout << answer << endl;
    }
}