【题解】中二之路

题意

给你一个的矩阵，每个位置上的元素为或，问你从左上角走到右下角，只能向下或向右走，且路程上的数之积为的路径有多少条呢。

题解

由于，一共有种选择方法，直接的话肯定会超时的，那么折半搜索，先做一遍从搜索到中间值，即的位置，然后记录中点的路径之积以及该积的路径条数，然后我们再从搜索回去，搜索回去的路径之积记为，那么我们去查第一次得到的有多少条，加入答案即可，注意的时中间点的元素是会被重复计算一次的。

复杂度

时间复杂度
##代码

#include<bits/stdc++.h>
using namespace std;
const int N=20+10;
int a[N][N];
map<long long,long long>mp[N][N];
long long k,ans=0;
int n,m;
void dfs1(int x,int y,long long num)
{
    if(x+y==(n+m+2)/2)
    {
        mp[x][y][num]++;
        return ;
    }
    if(x<n)
        dfs1(x+1,y,num*a[x+1][y]);
    if(y<m)
        dfs1(x,y+1,num*a[x][y+1]);
}
void dfs2(int x,int y,long long num)
{
    if(x+y==(n+m+2)/2)
    {
        ans+=mp[x][y][k/(num/a[x][y])];
        return ;
    }
    if(x>1)
        dfs2(x-1,y,num*a[x-1][y]);
    if(y>1)
        dfs2(x,y-1,num*a[x][y-1]);
}
int main()
{
    scanf("%d%d%lld",&n,&m,&k);
    ans=0;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
            scanf("%d",&a[i][j]);
    }
    dfs1(1,1,a[1][1]);
    dfs2(n,m,a[n][m]);
    printf("%lld\n",ans);
}