我的天哪我居然在 30 分钟内切了一道紫题？？？

看到标签分块直接进来了，第一眼感觉是整除分块。

哦，看来就是整除分块。

推了半天整理出一个性质：

若 $a_1,a_2$ 同属于一个块 $(\frac{n}{x},\frac{n}{x+1}]$ 中，则对于任意正整数 $p$，$pa_1,pa_2$ 也都属于一个块中。

证明过程我不太想写了，反证法即可。

好了那就开 $2$ 个 dp 数组吧，一个维护 $\sqrt{n}$ 个整除分块，一个维护剩下的没被分进块里的小数字。

时间复杂度 $O(rs\sqrt{n}\log(\sqrt{n}))$，空间的话可以滚动数组优化掉一维。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1010,M=310,P=1e9+7;
int dp[2][M][N],dp1[2][M][N],pos[N],B,D;
int a[M][M];
int get(int x){return upper_bound(pos+1,pos+B+1,x)-pos-1;}
signed main()
{
	int n,m,K;cin>>n>>m>>K;B=sqrt(K);
	for(int i=1;i<=B;i++)pos[i]=ceil(1.0*K/(B-i+1));D=pos[1]-1;
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>a[i][j];
	dp[0][1][1]=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			for(int k=1;k<=D;k++)
			{
				int x=k*a[i][j],id=get(x);
				if(id==0)
					dp[1][j][x]=(dp[1][j][x]+dp[0][j][k])%P,
					dp[1][j][x]=(dp[1][j][x]+dp[1][j-1][k])%P;
				else
					dp1[1][j][id]=(dp1[1][j][id]+dp[0][j][k])%P,
					dp1[1][j][id]=(dp1[1][j][id]+dp[1][j-1][k])%P;
			}
			for(int k=1;k<=B;k++)
			{
				int x=pos[k]*a[i][j],id=get(x);
				dp1[1][j][id]=(dp1[1][j][id]+dp1[0][j][k])%P;
				dp1[1][j][id]=(dp1[1][j][id]+dp1[1][j-1][k])%P;
			}
		}
		for(int j=1;j<=m;j++)for(int k=1;k<=D;k++)dp[0][j][k]=dp[1][j][k],dp[1][j][k]=0;
		for(int j=1;j<=m;j++)for(int k=1;k<=B;k++)dp1[0][j][k]=dp1[1][j][k],dp1[1][j][k]=0;
	}
	cout<<dp1[0][m][B];
	return 0;
}

题意

有一个 $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]);
}