题解：P5307 [COCI 2018/2019 #6] Mobitel

dayz_break404 · 2025-08-29 17:08:27 · 题解

七夕节到了没人一起过，只能录一个不错的 trick 了。

显然有一个三维的 dp_{i,j,k} 表示当前在 (i,j) 路径乘积为 k 的方案数。考虑优化其状态，类似数论分块地，我们将第三维变成至少乘上 k 才能大于等于 n 的方案数，这样的 k 是 O(\sqrt{n}) 级别的。

直接 dp 即可，时间复杂度 O(rs\sqrt{n})。

代码：

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x*f;
}
bool mbs;
const int mod=1e9+7;
const int maxn=320;
const int maxm=3e3+20;
const int maxk=1e6+20;
#define ll long long
int n,m,a[maxn][maxn],k,dp[2][maxn][maxm],rec[maxm],idx,id[maxk];
#define qx(x,y) id[((x)/(y)+((x)%(y)!=0))]
bool mbt;
int main(){
//  cerr<<(&mbs-&mbt)/1024.0/1024.0<<endl;
    n=read(),m=read(),k=read();
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) a[i][j]=read();
    for(int i=1;i<=k;i++) rec[++idx]=(k/i+(k%i!=0));
    sort(rec+1,rec+1+idx);
    idx=unique(rec+1,rec+1+idx)-rec-1;
    for(int i=1;i<=idx;i++) id[rec[i]]=i;
    for(int i=1;i<=n;i++){
        int cur=(i&1);
        for(int j=1;j<=m;j++){
            for(int c=1;c<=idx;c++) dp[cur][j][c]=0;
            if(i==1&&j==1){dp[cur][j][qx(k,a[i][j])]=1;continue;}
            if(i!=1)
                for(int c=1;c<=idx;c++) dp[cur][j][qx(rec[c],a[i][j])]=(dp[cur][j][qx(rec[c],a[i][j])]+dp[cur^1][j][c])%mod;
            if(j!=1)
                for(int c=1;c<=idx;c++) dp[cur][j][qx(rec[c],a[i][j])]=(dp[cur][j][qx(rec[c],a[i][j])]+dp[cur][j-1][c])%mod;
        }
    }
    printf("%d\n",dp[n&1][m][1]);
    return 0;
}