CF1794D 题解

yhy-trh / 2023-05-08 / 原文

一、题目描述：

　　一个正整数 $m$ 可以被唯一分解成 $p_1^{e_1} \times p_2^{e_2} \times ...\times p_k^{e_k}$ 的形式，其中 $p_1,p_2,...,p_k$为互不相同的质数，$e_1,e_2,...,e_k$ 为正整数。

　　定义一个可重集 $f(m)$ 为 $\{p_1,e_1,p_2,e_2,...,p_k,e_k\}$ 。现在给定正整数 $n$ 和大小为 $2\times n$ 集合 $S$ ，求有多少个 $m$ 能使得 $f(m)=S$。

　　由于答案可能很大，请对 $998$ $244$ $353$ 取模。数据范围：$1\leq n\leq 2022$。

二、解题思路：

　　思路不是我的，我是看一个同学的代码看懂的。

　　其实比较容易想到要统计素数个数，合数个数，然后套组合数多重集的板子。

　　但是方案数很多，甚至可能有 $2^n$ 种，所以我考场没做出来。

　　说到方案数，其实是一个计数 $dp$，但我对 $dp$ 本来就一窍不通，所以没做出来也很正常。

　　用一个类似背包的数组 $f_{i,j}$ 来表示状态，笼统一点理解：$f_{i,j}$ 表示选了前 $i$ 个数中的 $j$ 个数作底数的方案数。

　　但实际上并不完全是这样，因为有一部分质数也有可能做质数，所以还乘了逆元。看代码就知道了。时间复杂度 $O(n^2)$。

三、完整代码：

 1 #include<iostream>
 2 #define N 4050
 3 #define M 1000010
 4 #define lim 1000000
 5 #define ll long long
 6 #define mod 998244353
 7 using namespace std;
 8 ll n,cp,cc,cnt,ans;
 9 ll a[N],s[M],v1[M],v2[M],pri[M];
10 ll jc[M],inv[M],f[N][N],p[N],c[N];
11 void Prime()
12 {
13     for(ll i=2;i<=lim;i++)
14     {
15         if(!v1[i])    pri[++cnt]=i;
16         for(ll j=1;j<=cnt;j++)
17         {
18             if(i*pri[j]>lim)
19                 break;
20             v1[i*pri[j]]=1;
21             if(i%pri[j]==0)
22                 break;
23         }
24     }
25 }
26 ll qsm(ll base,ll q)
27 {
28     ll res=1;
29     while(q)
30     {
31         if(q&1)    res*=base,res%=mod;
32         base*=base,base%=mod,q>>=1;
33     }
34     return res;
35 }
36 void pre_work()
37 {
38     Prime();
39     v1[1]=jc[0]=1;
40     for(ll i=1;i<=lim;i++)
41         jc[i]=jc[i-1]*i%mod;
42     inv[lim]=qsm(jc[lim],mod-2);
43     for(ll i=lim;i>=1;i--)
44         inv[i-1]=inv[i]*i%mod;
45 }
46 int main()
47 {
48     ios::sync_with_stdio(false);
49     cin.tie(0);cout.tie(0);
50     cin>>n;pre_work();
51     for(ll i=1;i<=n*2;i++)
52     {
53         cin>>a[i],s[a[i]]++;
54         if(!v2[a[i]])
55             if(!v1[a[i]])    p[++cp]=a[i],v2[a[i]]=1;
56             else            c[++cc]=a[i],v2[a[i]]=1;
57     }
58     for(ll i=0;i<=cp;i++)
59         f[i][0]=1;
60     for(ll i=1;i<=cp;i++)
61         for(ll j=0;j<=n;j++)
62         {
63             f[i][j]=f[i-1][j-1]*inv[s[p[i]]-1]%mod;
64             (f[i][j]+=f[i-1][j]*inv[s[p[i]]])%=mod;
65         }
66     ans=f[cp][n]*jc[n]%mod;
67     for(ll i=1;i<=cc;i++)
68         (ans*=inv[s[c[i]]])%=mod;
69     cout<<ans<<'\n';
70     return 0;
71 }