Submission #45896262

---

Source Code Expand

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <set>
#include <iomanip>
#include <array>
#include <algorithm>
#include <random>
#include <chrono>
#include <assert.h>
#include <cstring>
#include <stack>
 
using namespace std;
 
// #defines
#define mkuni(v) sort(all(v)); v.erase(unique(all(v)), v.end())
#define all(v) v.begin(), v.end()
#define endl '\n'
#define ll long long
#define vint vector<int>
#define vll vector<ll>
#define vvint vector<vector<int>>
#define watch(x) dbg((#x), " : ", (x), '\n')
// #define watch(x) cerr << #x << " : " << (x) << '\n';
 
#ifndef ONLINE_JUDGE
#define DEBUG true
#endif
 
 
// ----------------------------------------------
// print statements
// ----------------------------------------------
template<typename T>
istream& operator>>(istream &in, vector<T> &v) {
    for (auto &x : v) in >> x;
    return in;
}
template<typename T>
ostream& operator<<(ostream &out, vector<T> &v) {
    out << "{";
    for (auto &x : v) out << x << " ";
    out << "}\n";
    return out;
}
template<typename Iterable>
void prnv(const Iterable& iterable, ostream&out = cout) {
    if (iterable.begin() == iterable.end()) {
        out << endl;
        return;
    }
    auto x = iterable.begin();
    out << *x;
    for (++x; x != iterable.end(); ++x) out << ' ' << *x;
    out << endl;
}
void prn(char en = '\n') {
    cout << en;
}
template<typename T, typename... Args>
void prn(T x, Args... args) {
    cout << x << " ";
    prn(args...);
}
void dbg() {
    cerr << endl;
}
#ifdef DEBUG
template<typename T, typename... Args>
void dbg(T x, Args... args) {
    cerr << x << " ";
    dbg(args...);
}
#else
template<typename T, typename... Args>
void dbg(T x, Args... args) {}
#endif
 
// ----------------------------------------------
 
/* ----------------------------------------------
 * Juvenile shortcuts
 * ---------------------------------------------- */
template<typename T> void setmin(T &a) {}
template<typename T, typename... Args> void setmin(T &a, T b, Args... args) {a = (a > b ? b : a); setmin(a, args...);}
template<typename T> void setmax(T &a) {}
template<typename T, typename... Args> void setmax(T &a, T b, Args... args) {a = (a < b ? b : a); setmax(a, args...);}
// ----------------------------------------------
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rand(l, r) uniform_int_distribution<ll>(l, r)(rng)
 
// const int MOD = (int)1e9 + 7;
const int MOD = 998244353;
const int oo = (int)1e9;
const int N = 17;
const int M = (int)1e5 + 5;

const int TSZ = (int)1e7;

// #define DEBUG false

ll dp[1<<N], ways[1<<N], diffcnt[1<<N], rcnt[1<<N], r[N], b[N], fac[M+5], invfac[M+5];

ll powermod(ll a, ll b) {
    if (b == 0) return 1;
    ll res = powermod(a, b>>1);
    res = (res * res) % MOD;
    if (b & 1) {
        res = (res * a) % MOD;
    }
    return res;
}

void solve() {

    int n, m;
    cin >> n >> m;

    for (int i=0;i<m;++i) {
        int x;
        cin >> x; --x;
        r[x]++;
    }

    for (int i=0;i<m;++i) {
        int x;
        cin >> x; --x;
        b[x]++;
    }

    fac[0] = 1;
    for (int i=1;i<M+5;++i) {
        fac[i] = (fac[i-1] * i) % MOD;
    }
    invfac[M+4] = powermod(fac[M+4], MOD-2);
    for (int i=M+3;i>=0;--i) {
        invfac[i] = (invfac[i + 1] * (i + 1)) % MOD;
    }

    dp[0] = 0;
    ways[0] = 1;
    rcnt[0] = 0;
    for (int mask=1;mask<(1<<n);++mask) {
        int i;
        for (int j=0;j<n;++j) if (mask & (1<<j)) {
            i = j;
            diffcnt[mask] = diffcnt[mask^(1<<j)] + r[j] - b[j];
            rcnt[mask] = rcnt[mask^(1<<j)] + r[j];
            break; 
        }
        int sz = rcnt[mask];

        if (diffcnt[mask] == 0) ways[mask] = fac[rcnt[mask]];
        else continue;

        for (int m=(mask-1);m>0;m=(m-1)&mask) {
            if ((m & (1<<i)) && diffcnt[m] == 0) {   
                int msz = rcnt[m];

                // prn("adding ", m, " to ", mask, " got ", dp[m], dp[mask^m]);

                ways[mask] -= (ways[m] * fac[sz-msz]) % MOD;
                if (ways[mask] < 0) ways[mask] += MOD;

                ll partways = (ways[m] * fac[sz - msz]) % MOD;
                dp[mask] += ((1 + dp[mask^m]) * partways) % MOD;
                if (dp[mask] >= MOD) dp[mask] -= MOD;
            }   
        }
        // prn(dp[mask], mask, " got last");
        dp[mask] += ways[mask];
        if (dp[mask] >= MOD) dp[mask] -= MOD;
        // prn(dp[mask], mask, " got last");
        dp[mask] = (dp[mask] * invfac[sz]) % MOD;
    }

    // for (int i=0;i<(1<<n);++i) prn(ways[i], " at mask = " , i);

    prn(dp[(1<<n)-1]);
}
 
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cout << fixed << setprecision(10);
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

Submission Info

Compile Error

./Main.cpp:79:12: warning: unused parameter 'x' [-Wunused-parameter]
void dbg(T x, Args... args) {}
           ^
./Main.cpp:79:23: warning: unused parameter 'args' [-Wunused-parameter]
void dbg(T x, Args... args) {}
                      ^
./Main.cpp:87:37: warning: unused parameter 'a' [-Wunused-parameter]
template<typename T> void setmin(T &a) {}
                                    ^
./Main.cpp:89:37: warning: unused parameter 'a' [-Wunused-parameter]
template<typename T> void setmax(T &a) {}
                                    ^
./Main.cpp:98:11: warning: unused variable 'oo' [-Wunused-const-variable]
const int oo = (int)1e9;
          ^
./Main.cpp:102:11: warning: unused variable 'TSZ' [-Wunused-const-variable]
const int TSZ = (int)1e7;
          ^
6 warnings generated.

Judge Result