2023 Hubei Provincial Collegiate Programming Contest

https://codeforces.com/gym/104337

E. Inverse Counting Path

题意

构造一个 $n\times n$ 的 $01$ 矩阵。要求从左上角走到右下角，每次向右或向下且只经过 $1$ 的路径恰有 $x$ 条。

数据范围：$n\leq 30,x\leq 10^9$。

题解

很酷炫的一道题！

首先，有一种基于二进制的构造方式：

1 1 1 1 1 1 1 1 1 1    (2^0)
1 1 0 0 0 0 0 0 0 1    
0 1 1 1 1 1 1 1 1 1    (2^1)
0 1 1 0 0 0 0 0 0 1    
0 0 1 1 1 1 1 1 1 1    (2^2)
0 0 1 1 0 0 0 0 0 1    
0 0 0 1 1 1 1 1 1 1    (2^3)
0 0 0 1 1 0 0 0 0 1
0 0 0 0 1 1 1 1 1 1    (2^4)
0 0 0 0 1 1 0 0 0 1 
0 0 0 0 0 1 1 1 1 1    (2^5)
0 0 0 0 0 1 1 0 0 1 
0 0 0 0 0 0 1 1 1 1    (2^6)
0 0 0 0 0 0 1 1 0 1

一个 $2\times 2$ 的全 $1$ 矩阵可以提供两种走法，在传到下一个 $2\times 2$ 的全 $1$ 矩阵就是四种走法，依次类推。同时，我们将每个 $2\times 2$ 连到最右边，就可以传递 $2$ 的幂次，如图所示。

但是，我们一共需要 $30$ 个这样的矩阵，需要 $n=60$，超出了限制。所以，得换一种更优的构造方法：

这是一种基于六进制的构造方式，我们使用 $3\times 3$ 的矩阵，每个提供了 $6$ 种走法，一共需要 $12$ 个这样的矩阵。同时，我们向右侧连线时可以构造出 $0\sim 5$ 种走法，参考图中右边和下边的方框。同时，我们向右传递和向下传递交错进行，这样相邻两个位之间不会发生相接。

我们发现这种方式刚好用满了 $30$ 个格子：最后一个矩阵与边界的距离为 $5$，而构造 $4$ 种走法需要一个 $2\times 4$ 的矩形。

最后贴一下丑陋的代码实现。

代码

#include <bits/stdc++.h>
using namespace std;
int a[35][35],b[15];
void add(int pos,int val)
{
    if(!val) return;
    if(pos&1) 
    {
        for(int i=2*pos+3;i<=30;i++) a[i][pos*2+1]=1;
        if(val==2) a[29][pos*2+1]=a[29][pos*2+2]=a[30][pos*2+1]=a[30][pos*2+2]=1;
        else if(val==3) a[28][pos*2+1]=a[28][pos*2+2]=a[29][pos*2+1]=a[29][pos*2+2]=a[30][pos*2+1]=a[30][pos*2+2]=1;
        else if(val==4) a[27][pos*2+1]=a[27][pos*2+2]=a[28][pos*2+1]=a[28][pos*2+2]=a[29][pos*2+1]=a[29][pos*2+2]=a[30][pos*2+1]=a[30][pos*2+2]=1;
        else if(val==5) a[28][pos*2+1]=a[28][pos*2+2]=a[29][pos*2+1]=a[29][pos*2+2]=a[29][pos*2+3]=a[30][pos*2+1]=a[30][pos*2+2]=a[30][pos*2+3]=1;
    }
    else
    {
        for(int i=2*pos+3;i<=30;i++) a[pos*2+1][i]=1;
        if(val==2) a[pos*2+1][29]=a[pos*2+2][29]=a[pos*2+1][30]=a[pos*2+2][30]=1;
        else if(val==3) a[pos*2+1][28]=a[pos*2+2][28]=a[pos*2+1][29]=a[pos*2+2][29]=a[pos*2+1][30]=a[pos*2+2][30]=1;
        else if(val==4) a[pos*2+1][27]=a[pos*2+2][27]=a[pos*2+1][28]=a[pos*2+2][28]=a[pos*2+1][29]=a[pos*2+2][29]=a[pos*2+1][30]=a[pos*2+2][30]=1;
        else if(val==5) a[pos*2+1][28]=a[pos*2+2][28]=a[pos*2+1][29]=a[pos*2+2][29]=a[pos*2+3][29]=a[pos*2+1][30]=a[pos*2+2][30]=a[pos*2+3][30]=1;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    for(int i=0;i<=11;i++)
        for(int j=1;j<=3;j++)
            for(int k=1;k<=3;k++) a[i*2+j][i*2+k]=1;
    for(int i=1;i<=30;i++) a[i][30]=a[30][i]=1;
    int x;cin>>x;
    int len=0;
    while(x>0)
    {
        b[len++]=x%6;
        x/=6;
    }
    for(int i=0;i<len;i++) add(i,b[i]);
    cout<<30<<'\n';
    for(int i=1;i<=30;i++)
        for(int j=1;j<=30;j++) cout<<a[i][j]<<" \n"[j==30];
    return 0;
}