题解 P5307 【[COCI2019] Mobitel】

· · 题解

题意

有一个 r\times c 的矩阵 a，矩阵的每个位置都有一个正整数，求从左上角走到右下角并且满足路径上数字乘积之和大于 n 的方案数。

\texttt{Data Range:}1\leq r,c\leq 300,1\leq n\leq 10^6

题解

不一定更好的阅读体验

本人的本命题居然是个 DP + 整除分块呢。

草哦为什么这个题目名字叫手机啊我怎么看了半天没有看出与手机的任何关联呢

首先考虑一个非常 naive 的 DP，设 f_{i,j,k} 表示在 (i,j) 位置，已经走过的路径乘积之和为 k 的方案数，那这个东西很明显由于复杂度上天显得非常不可做。

于是我们可以换个方向去思考这个问题，设 f_{i,j,k} 表示在 (i,j) 位置还需要乘上 k，路径的乘积才能超过 n，这样子的话转移其实也很好写，但是毕竟状态的数量还是太庞大了，复杂度依旧上天。

这个时候注意到 k 这个维度上的取值很少，根据整除分块的理论只会有 O(\sqrt{n}) 种，所以可以考虑对所有真正有用的值来 DP，这个时候只需要预处理出每一个可能的取值对应哪个块即可做到 O(rc\sqrt{n})。

注意到这东西空间会超，所以考虑对 i 这一位滚一下就好了。同时，代码细节贼多，稍不注意就会挂成狗。这个版本的代码跑的贼慢，看看到时候来卡卡常什么的。

代码

#include<bits/stdc++.h>
#define dv(x,y) ((x)/(y)+!!((x)%(y)))
using namespace std;
typedef int ll;
typedef long long int li;
const ll MAXN=1e6+51,MOD=1e9+7;
ll r,c,n,blkc;
ll x[351][351],d[MAXN],rv[MAXN],f[2][351][2051],blk[2051];
inline ll read()
{
    register ll num=0,neg=1;
    register char ch=getchar();
    while(!isdigit(ch)&&ch!='-')
    {
        ch=getchar();
    }
    if(ch=='-')
    {
        neg=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        num=(num<<3)+(num<<1)+(ch-'0');
        ch=getchar();
    }
    return num*neg;
}
int main()
{
    r=read(),c=read(),n=read();
    for(register int i=1;i<=r;i++)
    {
        for(register int j=1;j<=c;j++)
        {
            x[i][j]=read();
        }
    }
    for(register int i=1;i<=n;i++)
    {
        (d[i]=dv(n,i))!=d[i-1]?blk[++blkc]=d[i],rv[d[i]]=blkc:1;
    }
    f[1][1][rv[dv(n,x[1][1])]]=1;
    for(register int i=1;i<=r;i++)
    {
        for(register int j=1;j<=c;j++)
        {
            for(register int k=1;k<=blkc;k++)
            {
                if(i!=r)
                {
                    ll &s=f[(i&1)^1][j][rv[dv(blk[k],x[i+1][j])]];
                    s=(s+f[i&1][j][k])%MOD;
                }
                if(j!=c)
                {
                    ll &s=f[i&1][j+1][rv[dv(blk[k],x[i][j+1])]];
                    s=(s+f[i&1][j][k])%MOD;
                }
                (i!=r||j!=c||k!=blkc)?f[i&1][j][k]=0:1;
            }
        }
    }
    printf("%d\n",f[r&1][c][blkc]);
}