Submission #45919384

---

Source Code Expand

// Om Namah Shivaya

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x, y) ((x + y - 1) / (y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i, n) for(int i = 0; i < n; ++i)
#define rep1(i, n) for(int i = 1; i <= n; ++i)
#define rev(i, s, e) for(int i = s; i >= e; --i)
#define trav(i, a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a, b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a, b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*



*/

const int MOD = 998244353;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

ll fact[N], ifact[N];

ll bexp(ll a, ll b) {
    a %= MOD;
    if (a == 0) return 0;

    ll res = 1;

    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }

    return res;
}

ll invmod(ll a) {
    return bexp(a, MOD - 2);
}

ll ncr(ll n, ll r) {
    if (n < 0 or r < 0 or n < r) return 0;
    return fact[n] * ifact[r] % MOD * ifact[n - r] % MOD;
}

ll npr(ll n, ll r) {
    if (n < 0 or r < 0 or n < r) return 0;
    return fact[n] * ifact[n - r] % MOD;
}

void precalc(ll n) {
    fact[0] = 1;
    rep1(i, n) fact[i] = fact[i - 1] * i % MOD;

    ifact[n] = invmod(fact[n]);
    rev(i, n - 1, 0) ifact[i] = ifact[i + 1] * (i + 1) % MOD;
}

void solve(int test_case)
{
    precalc(N-1);

    ll n,m; cin >> n >> m;    
    vector<ll> a(m), b(m);
    rep(i,m) cin >> a[i], a[i]--;
    rep(i,m) cin >> b[i], b[i]--;

    vector<ll> cnta(n), cntb(n);
    rep(i,m) cnta[a[i]]++;
    rep(i,m) cntb[b[i]]++;

    vector<ll> dp1(1<<n), dp2(1<<n);

    rep(mask,1<<n){
        if(!mask) conts;

        ll ca = 0, cb = 0;
        rep(i,n){
            if(mask & (1<<i)){
                ca += cnta[i];
                cb += cntb[i];
            }
        }

        dp1[mask] = fact[ca];

        for(int s = (mask-1)&mask; s; s = (s-1)&mask){
            if((s&-s) == (mask&-mask)){
                dp1[mask] -= dp1[s]*dp2[mask^s];
                dp2[mask] += dp1[s]*dp2[mask^s];
                dp1[mask] = (dp1[mask]%MOD+MOD) % MOD;
                dp2[mask] = (dp2[mask]%MOD+MOD) % MOD;   
            }
        }

        if(ca != cb){
            dp1[mask] = 0;
        }

        dp2[mask] += dp1[mask];
        dp2[mask] %= MOD;
    }

    ll ans = 0;
    rep(mask,1<<n){
        ll sum = 0;
        rep(i,n){
            if(mask & (1<<i)){
                sum += cnta[i];
            }
        }

        ll ways = dp1[mask]*fact[m-sum] % MOD;
        ans += ways;
        ans %= MOD;
    }

    ans = ans*ifact[m] % MOD;
    cout << ans << endl;
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘void solve(int)’:
Main.cpp:101:16: warning: unused parameter ‘test_case’ [-Wunused-parameter]
  101 | void solve(int test_case)
      |            ~~~~^~~~~~~~~

Judge Result