粗糙的基础做法

100 分

实际上显然 a 数组里面数值大小无所谓，只需要关注每一行有多少个数即可。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 100000;
const int MOD = 1'000'000'000 + 1;
int n;
bool vis[MAXN + 5];
// 生成 B 左上角的 n 以内的矩阵
int N, M;
int a[18][12]; // log3(n)~17 log2(n)~11
void gen(int B)
{
    N = 17;
    M = 11;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            if (i == 1 && j == 1)
                a[i][j] = B;
            else if (j == 1)
                a[i][j] = a[i - 1][j] * 2;
            else
                a[i][j] = a[i][j - 1] * 3;
            if (a[i][j] > n)
                a[i][j] = 0;
            if (i == 1 && a[i][j] == 0)
            {
                M = j - 1;
                break;
            }
        }
        if (a[i][1] == 0)
        {
            N = i - 1;
            break;
        }
    }
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            vis[a[i][j]] = true;
            // cout << a[i][j] << " ";
        }
        // cout << "\n";
    }
    // cout << "=====\n";
}
// 计算矩阵值前 i 行，第 i 行选了 sta 的方案数
int f[25][1 << 11];
int cal()
{
    int res = 0;
    f[0][0] = 1;
    for (int i = 1; i <= N; i++)
        for (int sta = 0; sta <= (1 << M) - 1; sta++)
        {
            f[i][sta] = 0;
            bool flag = true; // 状态是否合法
            for (int j = 0; j <= M - 1; j++)
                if ((sta & (1 << j)) && a[i][j + 1] == 0)
                {
                    flag = false;
                    break;
                }
            if (!flag || (sta & (sta << 1)))
                continue;
            for (int pre = 0; pre <= (1 << M) - 1; pre++)
            {
                if (sta & pre)
                    continue;
                f[i][sta] += f[i - 1][pre];
            }
            if (i == N)
            {
                res += f[i][sta];
                res %= MOD;
            }
        }
    return res;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    int ans = 1;
    for (int i = 1; i <= n; i++)
    {
        if (vis[i])
            continue;
        gen(i);
        ans *= cal();
        ans %= MOD;
    }
    cout << ans;
    return 0;
}