CF1794D 题解

一、题目描述：

　　一个正整数 $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,ans,cnt,ch,cp;
 9 ll a[N],p[N],h[N],s[M],f[N][N];
10 ll v1[M],v2[M],jc[M],inv[M],pri[M];
11 ll qsm(ll base,ll q)
12 {
13     ll res=1;
14     while(q)
15     {
16         if(q&1)    res*=base,res%=mod;
17         base*=base;base%=mod;q>>=1;
18     }
19     return res;
20 }
21 void pre_work()
22 {
23     v1[1]=jc[0]=1;
24     for(ll i=1;i<=lim;i++)
25         jc[i]=jc[i-1]*i%mod;
26     inv[lim]=qsm(jc[lim],mod-2);
27     for(ll i=lim-1;i>=0;i--)
28         inv[i]=inv[i+1]*(i+1)%mod;
29     for(ll i=2;i<=lim;i++) 
30     {
31         if(!v1[i]) pri[++cnt]=i;
32         for(ll j=1;j<=cnt;j++)
33         {
34             if(i*pri[j]>lim)
35                 break;
36             v1[i*pri[j]]=1;
37             if(i%pri[j]==0)
38                 break;
39         }
40     }
41 }
42 int main()
43 {
44     ios::sync_with_stdio(false);
45     cin.tie(0);cout.tie(0);
46     cin>>n;pre_work();
47     for(ll i=1;i<=n*2;i++)
48     {
49         cin>>a[i];s[a[i]]++; 
50         if(!v2[a[i]])
51         {
52             if(!v1[a[i]])    p[++cp]=a[i]; 
53             else            h[++ch]=a[i];
54             v2[a[i]]=1; 
55         }
56     }
57     for(ll i=0;i<=cp;i++)
58         f[i][0]=1;
59     for(ll i=1;i<=cp;i++)
60         for(ll j=0;j<=n;j++)
61         {
62             f[i][j]=f[i-1][j-1]*inv[s[p[i]]-1]%mod;
63             (f[i][j]+=f[i-1][j]*inv[s[p[i]]]%mod)%=mod;
64         }
65     ans=f[cp][n]*jc[n]%mod;
66     for(ll i=1;i<=ch;i++)
67         (ans*=inv[s[h[i]]])%=mod;
68     cout<<ans<<'\n';
69     return 0;
70 }

四、写题心得：

　　感觉有关阶乘，逆元的题都特别有意思，虽然我大多数都不会。不过加油吧！拜拜！