自动搬运

查看原文

来自洛谷，原作者为

	FFTotoro 龙猫

搬运于2025-08-24 22:51:35，当前版本为作者最后更新于2023-10-16 20:22:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

对于 $k\le 20$ 的部分分我们有一个比较简单的动态规划做法：令 $f_{i,j,w}$ 为从 $(1,1)$ 走到 $(i,j)$ 且路径上乘积除以 $k$ 的余数为 $w$ 的方案数，对于 $a_{i,j}\ge 0$ 的 $(i,j)$ 显然有 $f_{i,j,x\times a_{i,j}\bmod k}=f_{i-1,j,x}+f_{i,j-1,x}$，答案为 $f_{n,n,0}$。

但 $k=10^6$ 的时候这个做法是 $O(n^2k)$ 的，无法通过。

维护余数肯定是不行了；那么换个角度想，让上文 $w$ 的含义变为路径上的乘积 $p$ 与 $k$ 的最大公约数 $\gcd(p,k)$：只有 $\gcd(p,k)=k$ 时才有 $k|p$。因为 $\gcd(p,k)|k$，所以第三维的大小为 $k$ 的因数个数，可以证明在 $k\le 10^6$ 的情况下不超过 $300$ 个。

在转移过程中求最大公约数的时候会带个 $\log$，会被卡。可以先预处理一下 $k$ 的所有因数两两之间乘积与 $k$ 的最大公约数，然后对于每个输入的 $a_{i,j}\ge 0$ 都执行 $a_{i,j}\leftarrow\gcd(a_{i,j},k)$。转移为 $f_{i,j,\gcd(x\times a_{i,j},k)}=f_{i-1,j,x}+f_{i,j-1,x}$。

对于每个因数映射下标，方便转移。设 $k$ 映射的下标是 $x$，则答案为 $f_{n,n,x}$。时间复杂度 $O(k+d^2\log k+n^2d)$，其中 $d=300$，可以通过。

$63\mathrm{pts}$ 部分分代码（第一种思路）：

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int main(){
  ios::sync_with_stdio(false);
  int n,k; cin>>n>>k;
  vector a(n,vector<int>(n));
  for(auto &i:a)for(auto &j:i)cin>>j;
  vector f(n,vector(n,vector<int>(k)));
  f[0][0][a[0][0]%k]=1;
  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
      if(a[i][j]>=0)
        for(int l=0;l<k;l++){
          if(i)(f[i][j][1ll*l*a[i][j]%k]+=f[i-1][j][l])%=mod;
          if(j)(f[i][j][1ll*l*a[i][j]%k]+=f[i][j-1][l])%=mod;
        }
  cout<<f[n-1][n-1][0]<<endl;
  return 0;
}

$110\mathrm{pts}$ 满分代码（第二种思路）：

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int main(){
  ios::sync_with_stdio(false);
  int n,k; cin>>n>>k;
  vector<int> p,m(k+1);
  for(int i=1;i<=k;i++)
    if(!(k%i))m[i]=p.size(),p.emplace_back(i);
  vector g(p.size(),vector<int>(p.size()));
  for(int i=0;i<p.size();i++)
    for(int j=0;j<p.size();j++)
      g[i][j]=m[gcd(1ll*p[i]*p[j],k)];
  vector a(n,vector<int>(n));
  for(auto &i:a)for(auto &j:i)if(cin>>j;j>=0)j=m[gcd(j,k)];
  vector f(n,vector(n,vector<int>(p.size())));
  f[0][0][a[0][0]]=1;
  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
      if(a[i][j]>=0)
        for(int l=0;l<p.size();l++){
          if(i)(f[i][j][g[l][a[i][j]]]+=f[i-1][j][l])%=mod;
          if(j)(f[i][j][g[l][a[i][j]]]+=f[i][j-1][l])%=mod;
        }
  cout<<f[n-1][n-1].back()<<endl;
  return 0;
}