[COCI2022-2023 #3] Bomboni 题解
FFTotoro
·
·
题解
对于 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，可以通过。
```cpp
#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}$ 满分代码（第二种思路）：
```cpp
#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;
}
```