一、题目描述：
一个正整数 $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 }
四、写题心得：
感觉有关阶乘，逆元的题都特别有意思，虽然我大多数都不会。不过加油吧！拜拜！