1794D - Counting Factorizations - CodeForces Solution

// Just Not the Best :)

#include <bits/stdc++.h>
using namespace std;

//DataTypes
using str =  string;
using ll  =  long long;
using ld  =  long double;
using vl  =  vector<ll>;
using vs  =  vector<str>;
using vpl =  vector<pair<ll,ll>>;
using sll =  set<ll>;
using pll =  pair<ll,ll>;
#define mset multiset

//Shorts
#define pus     push_back
#define pub     pop_back
#define in      insert
#define ff      first
#define ss      second
#define dbg(x)  cout<<#x<<" = "<<x<<'\n';

//Functions
#define sz(x)     ((ll)(x).size())
#define all(x)    x.begin(),x.end()
#define srt(x)    sort(all(x))
#define srtd(x)   sort(x.rbegin(),x.rend())
#define rev(x)    reverse(all(x));
#define Vmax(x)   *max_element(all(x))
#define Vmin(x)   *min_element(all(x))
#define Vsum(x)   accumulate(all(x),0ll)
#define lowB(v,x) lower_bound(all(v),x)-v.begin()
#define upB(v,x)  upper_bound(all(v),x)-v.begin() 
#define ers(v,i)  v.erase(v.begin()+i) 
#define NextP(x)  next_permutation(all(x))
#define PrevP(x)  prev_permutation(all(x))
#define cntB(x)   __builtin_popcountll(x)  
#define cntC(s,x) ll(count(all(s),x))

//loops
#define For(n)      for (ll i = 0; i < n; i++)
#define ForR(n)     for (ll i = n-1; i >= 0; i--)
#define Forj(n)     for (ll j = 0; j < n; j++)
#define For1(n)     for (ll i = 1; i < n; i++)
#define Forl(x,y,z) for (ll x = y; x < z; x++)

//IO
#define nl       cout << "\n";
#define endl     "\n";
#define ya       cout << "YES\n";
#define na       cout << "NO\n";
#define prs(n)   fixed << setprecision(n)
#define inpt(v)  For(sz(v)) cin >> v[i];
#define prt(v)   {for(auto i:v) cout << i << " "; cout << "\n";}

//Constants
const int M = 998244353; 
const int N = 1e6+5;
const ld pi = 3.141592653589793238;
const ll INF = 2e18;

ll n, x, y, z, a, b, c, k, q, m; str s; 
vl isp(N,1), facs(4045,1);
ll dp[5001][2025];
map<ll,ll> mp;
 
//---------------------------------------------------------------------------------------------------------------------------------
//Let's Go :)

void impl()
{
      isp[0] = isp[1] = 0;

      for(ll i = 2; i < N; i++)
      {
            if(isp[i]==0) continue;
            for(ll j = 2*i; j < N; j+=i) isp[j] = 0;
      }

      For1(sz(facs)) facs[i] = (facs[i-1]*i)%M;
}

ll power(ll a, ll b)
{
      if(mp.count(a)) return mp[a];
      ll ans = 1, s = a;

      while(b)
      {
            if(b&1) ans = (ans*a)%M;
            a = (a*a)%M;
            b /= 2;
      }

      return mp[s] = ans;
}

ll recr(ll id, ll cnt, vpl &p)
{
      if(cnt<0) return 0;
      
      if(id==sz(p))
      {
            if(cnt==0) return 1;
            return 0;
      }

      if(dp[id][cnt]+1) return dp[id][cnt];

      ll ans1 = (recr(id+1,cnt,p)*power(facs[p[id].ss],M-2))%M, ans2 = 0;
      if(isp[p[id].ff]) ans2 = (recr(id+1,cnt-1,p)*power(facs[p[id].ss-1],M-2))%M;

      return dp[id][cnt] = (ans1+ans2)%M;
}

void solve()
{
      cin >> n;
      map<ll,ll> mp;
      vpl p;

      For(2*n)
      {
            cin >> x;
            mp[x]++;    
      }
      
      for(auto pr:mp) p.pus(pr);

      memset(dp,-1,sizeof(dp));

      cout << (facs[n]*recr(0,n,p))%M;
}

int main()
{
      impl();
      ios_base::sync_with_stdio(0); cin.tie(0);
      int t = 1;
      // cin >> t;
       
      while(t--) solve();

      return 0;
}