题解：CF1794D Counting Factorizations

· · 题解

题解

首先有一个显然的性质，就是说只要底数和指数有任一不同，那么最后的数一定不一样，因为给出的是分解质因数的形式。

所以说我们就无需考虑算重的事情了，接下来开始分类讨论。设不同的质数共出现了 x 个，我们就可以分三种情况。

第一种是 x < n，此时显然没有合法情况，答案是 0。

第二种是 x = n，此时我们选择的就是这 n 个质数，所以说直接可以用公式表示出结果，结果应为 \frac{n!}{\prod cnt_i}。其中 cnt_i 表示除去 n 个质数的各个数的出现次数。

最后就是 x > n，此时直接使用组合数显然不太好维护，所以说我们考虑设 dp_{i,j} 表示前 i 个数选了 j 个在指数集合里的方案数。那么初始化就是 dp_{0,0} = \frac{n!}{\prod cnt_i}。

考虑只有选与不选两种情况。因此可以得到转移式子。

dp_{i,j} = dp_{i-1,j} + dp_{i-1,j-1} \times \frac{2n-x+j}{1+cntt_i}

其中 cntt_i 表示对于指数集的数的出现次数。

答案就是 dp_{x,n-x}。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 998244353;
int a[5005];
int cntt[1000005];
int cnt[1000005],fact[1000005];
int cnttt[1000005];
int prime[1000005];
int dp[4405][4405];
int flag[1000005];
int p[1000005];
int n;
int poww(int x,int y)
{
    if(y==0) return 1;
    int anss = poww(x,y/2);
    if(y%2==0)
        return anss%mod*anss%mod;
    else
        return anss%mod*anss%mod*x%mod;

}
int solve()
{
    int qaq = 1;
    for(int i=1;i<=2*n;i++)
    {
        cntt[a[i]]++;
    }
    for(int i=1;i<=1000000;i++)
    {
        if(cntt[i]!=0)
        {
            if(cnt[i]==0)
                qaq = qaq*fact[cntt[i]]%mod;
            else
            {
                qaq = qaq*fact[cntt[i]-1]%mod;
                cntt[i]--;
            }
        }
    }
    return qaq;
}
signed main()
{
    scanf("%lld",&n);
    for(int i=1;i<=2*n;i++)
    {
        scanf("%lld",&a[i]);
    }
    fact[0] = 1;
    for(int i=1;i<=1000000;i++)
    {
        fact[i] = fact[i-1]*i%mod;
    }
    prime[0] = prime[1] = 1;
    for(int i=2;i*i<=1000000;i++)
    {
        if(prime[i]) continue;
        for(int j=i*2;j<=1000000;j+=i)
            prime[j] = 1;
    }
// 0 prime 1 not prime  
    int qwq = 0;
    for(int i=1;i<=2*n;i++)
    {
        if(prime[a[i]]==0)
        {
            cnt[a[i]]++;
            if(cnt[a[i]]==1)
                qwq++;
        }
    }
    if(qwq<n) puts("0");
    else
    {
        if(qwq==n)
        { 
            int qwq2 = solve();
            printf("%lld\n",fact[2*n-qwq]%mod*poww(qwq2,mod-2)%mod);
        }
        else
        {
            int qwq2 = solve();
            for(int i=1;i<=2*n;i++)
                cnttt[a[i]]++;
            int awa = 0;
            for(int i=1;i<=2*n;i++)
            {
                if(prime[a[i]]==0&&flag[a[i]]==0)
                {
                    p[++awa] = a[i];
                    cnttt[a[i]]--;
                    flag[a[i]] = 1;
                }
            }
            dp[0][0] = fact[2*n-qwq]%mod*poww(qwq2,mod-2)%mod;
            for(int i=1;i<=qwq;i++)
            {
                for(int j=0;j<=qwq-n&&j<=i;j++)
                {
                    if(!j) dp[i][j] = dp[i-1][j];
                    else dp[i][j] = (dp[i-1][j]%mod+1ll*dp[i-1][j-1]%mod*(2*n-qwq+j)%mod*poww((cnttt[p[i]]+1),mod-2))%mod;
                }
            }
            printf("%lld\n",dp[qwq][qwq-n]);
        }
    } 
}