没有发现整除分块性质导致的
ETO_leader
·
·
题解
记录一个魔怔做法，与目前所有题解都不一样。
题意简述
给定 n\times m 方格图，格子 (i,j) 有权值 a_{i,j}，定义一条路径 (x_1,y_1),(x_2,y_2) \dots (x_l,y_l) 的权值为 \prod\limits_{i=1}^l a_{x_i,y_i}。
现在你要从 (1,1) 走到 (n,m)，只能往右或往下走，问你可以走出的所有权值 \ge x 的路径条数。
### 做法
首先肯定是转化到权值 $\le k-1$ 的路径数计数。
然后我们有朴素的 DP，状态定义 $f(i,j,k)$ 表示走到 $(i,j)$ 权值为 $k$ 的方案数，转移显然。
考虑优化这个做法。
设置阈值 $c=\lceil \sqrt x\rceil$，则每条权值 $\le x-1$ 路径一定可以拆成一条从起点到某个中间点 $u$ 的路径 $l_1$，$u$ 的后继 $v$，和 $v$ 的后继到终点的路径 $l_2$，且 $l_1$，$l_2$ 的权值均不大于 $c$，证明显然。
然后我们利用上面那个性质，考虑如何统计答案。
设 $f(i,j,k)$ 表示从 $(1,1)$ 走到 $(i,j)$，路径权值为 $k$ 的方案数，且 $k \le c$。
设 $g(i,j,k)$ 表示从 $(i,j)$ 走到 $(n,m)$，**路径权值小于等于 $a_{i,j}\cdot k$** 的方案数，且 $k \le c$。
$f,g$ 都可以通过 dp 求出。
我们假设 $a_{1,1} \le c$，另外一种情况的统计答案方法是简单的。
则权值 $\le k-1$ 的路径数 $h$ 如下：
$$
\sum\limits_{i=1}^{n-1}\sum\limits_{j=1}^m\sum\limits_{k=1}^c f(i,j,k)g(i+1,j,\lfloor \frac{x}{a_{i+1,j}\cdot k}\rfloor)[a_{i+1,j}\cdot k > c]\\+
\sum\limits_{i=1}^n\sum\limits_{j=1}^{m-1}\sum\limits_{k=1}^c f(i,j,k)g(i,j+1,\lfloor \frac{x}{a_{i,j+1}\cdot k}\rfloor)[a_{i,j+1}\cdot k > c]\\
+\sum\limits_{k=1}^c f(n,m,c)
$$
用人话说就是计数路径上的第一个点 $u$ 使得起点到 $u$ 这条路径的权值 $> c$，容易发现是不重不漏的。
则最终的答案是 $\binom{n+m-2}{n-1}-h$。
注意模数是 $10^9+7$ 而不是 $998244353$，不要虚空调试。
时间复杂度 $O(nm\sqrt x)$，空间复杂度 $O(nm \sqrt x)$，实现上要将 $f$ 滚掉以优化空间。
### Code:
```cpp
#include<bits/stdc++.h>
#define cir(i,a,b) for(int i=a;i<b;++i)
using namespace std;
using lint=long long;
static constexpr auto MOD=(int)(1e9+7);
class mathbase{
private:
vector<lint> fct,ifct;
public:
constexpr auto qpow(lint a,auto b){
auto res=1ll;
while(b){
if(b&1) (res*=a)%=MOD;
(a*=a)%=MOD;b>>=1;
}
return res;
}
constexpr auto inv(auto x){return qpow(x,MOD-2);}
auto init(const auto n){
fct.resize(n,1);
cir(i,1,n) fct[i]=fct[i-1]*i%MOD;
ifct=fct;
for(auto&i:ifct) i=inv(i);
}
auto C(auto a,auto b){
if(a<b||b<0) return 0ll;
return fct[a]*ifct[b]%MOD*ifct[a-b]%MOD;
}
} math;
int main(){
ios::sync_with_stdio(false),cin.tie(nullptr);
int n,m,k;cin>>n>>m>>k;--k;math.init(n+m+7);
vector w(n,vector<lint>(m));
for(auto&x:w) for(auto&i:x) cin>>i;
const auto sqr=(int)(ceil(sqrtl(k)))+7;
vector f(2,vector(m,vector<int>(sqr))),g(n,vector(m,vector<int>(sqr)));
g[n-1][m-1][1]=1;
for(auto i=n-1;~i;--i) for(auto j=m-1;~j;--j) cir(wx,0,sqr) if(wx*w[i][j]<sqr){
if(i) (g[i-1][j][wx*w[i][j]]+=g[i][j][wx])%=MOD;
if(j) (g[i][j-1][wx*w[i][j]]+=g[i][j][wx])%=MOD;
}
cir(i,0,n) cir(j,0,m) cir(wx,1,sqr) (g[i][j][wx]+=g[i][j][wx-1])%=MOD;
auto ans=0ll;
auto cur=1;
if(w[0][0]<sqr) f[cur^1][0][w[0][0]]=1;
cir(i,0,n){
cur^=1;
f[cur^1]=vector(m,vector<int>(sqr));
cir(j,0,m) cir(wx,0,sqr){
if(i+1<n&&wx*w[i+1][j]<sqr) (f[cur^1][j][wx*w[i+1][j]]+=f[cur][j][wx])%=MOD;
if(j+1<m&&wx*w[i][j+1]<sqr) (f[cur][j+1][wx*w[i][j+1]]+=f[cur][j][wx])%=MOD;
if(i+1<n&&wx*w[i+1][j]>sqr-1) (ans+=(lint)(f[cur][j][wx])*(g[i+1][j][k/(wx*w[i+1][j])]))%=MOD;
if(j+1<m&&wx*w[i][j+1]>sqr-1) (ans+=(lint)(f[cur][j][wx])*(g[i][j+1][k/(wx*w[i][j+1])]))%=MOD;
}
}
cir(wx,0,sqr) (ans+=f[cur][m-1][wx])%=MOD;
if(w[0][0]>sqr-1) (ans+=g[0][0][k/w[0][0]])%=MOD;
cout<<(math.C(n+m-2,n-1)+MOD-ans)%MOD<<'\n';
return 0;
}
```