[ARC192D] Fraction Line 题解

FFTotoro · 2025-02-11 17:23:19 · 题解

令 d_p(x) 为 x 的标准质因数分解式中质数 p 的指数，即最大的非负整数 k 使得 p^k|x。

对于每个质因数 p 单独考虑合法序列数量，即对于序列 A' 满足 A'_i=p^{d_p(A_i)} 求解原问题。最后将所有答案相乘即为最终答案。

考虑求解这个修改后的问题：对题目中的 f 函数进行一些简单的推导：f\left(\dfrac{p^x}{p^y}\right)=\dfrac{p^xp^y}{p^{2\!\min\{x,y\}}}=p^{|x-y|}。于是题目条件可以改写为如下形式：

令 d_p(A_i)=C_i。设计动态规划 g_{i,j,k} 表示考虑了 S 的前 i 个元素，满足 d_p(S_i)=j，k\in\{0,1\} 表示是否存在 S_x(1\le x\le i) 满足 d_p(S_x)=0 的方案数。根据上面 f 的定义，可以推导出转移方程：

上述的 \lor 表示析取。其中第二维的值域为 \left[0,\sum\limits_{i=1}^{N-1}C_i\right]。实现时可以使用滚动数组把第一维滚掉。

时间复杂度 O(N\sqrt{\max A_i}+N^2\log\max A_i)。前者是分解质因数，后者是 DP。

放代码：

#include<bits/stdc++.h>
using namespace std;
const int P=998244353,V=1e3;
inline void chadd(int &x,int y){
  if((x+=y)>=P)x-=P;
}
bitset<V+1> b;
int main(){
  ios::sync_with_stdio(false);
  int n,q=1; cin>>n;
  vector<int> a(n-1),p;
  vector c(n-1,vector<int>(V+1));
  for(auto &i:a)cin>>i;
  for(int i=0;i<n-1;i++){
    int x=a[i];
    for(int j=2;j*j<=x;j++)
      while(!(x%j))c[i][j]++,x/=j;
    if(x>1)c[i][x]++;
  } // 进行分解质因数
  for(int i=2;i<=V;i++)
    if(!b[i]){
      p.emplace_back(i);
      for(int j=i<<1;j<=V;j+=i)
        b[j]=true;
    } // 筛质数
  for(int i:p){
    int s=1,w=0;
    for(int j=0;j<n-1;j++)
      s+=c[j][i];
    vector f(s+1,vector<int>(2));
    vector<int> pw(s+1);
    for(int j=0;j<=s;j++)
      f[j][!j]=pw[j]=j?1ll*pw[j-1]*i%P:1;
    // 预处理 p 的 k 次幂，作为 DP 初始值
    for(int j=0;j<n-1;j++){
      vector g(s+1,vector<int>(2));
      for(int k=0;k<=s;k++)
        for(int b=0;b<2;b++){
          if(k+c[j][i]<=s)chadd(g[k+c[j][i]][b|!(k+c[j][i])],1ll*f[k][b]*pw[k+c[j][i]]%P);
          if(c[j][i]&&k>=c[j][i])chadd(g[k-c[j][i]][b|!(k-c[j][i])],1ll*f[k][b]*pw[k-c[j][i]]%P);
        }
      f=g;
    } // 模拟上述的 DP 过程
    for(auto v:f)chadd(w,v[1]);
    q=1ll*q*w%P; // 将所有答案相乘
  }
  cout<<q<<endl;
  return 0;
}