Submission #49762974

---

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/modint>
const int MOD=998244353;
using mint = atcoder::static_modint<MOD>;
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)(n);i++)
ll read(){ll r;scanf("%lld",&r);return r;}
const int N=17;
mint f[1<<N]; // = mask内连成一个连通块 且无剩余蓝红的方案数
mint g[1<<N]={1}; // = mask内无剩余蓝红的方案数, 红=蓝， g[] = 个数!
mint ans[1<<N]; //  sum s的所有方案的连通块个数
array<int,2> rb[1<<N];
array<int,2> rbm[1<<N]; // red blue mask
int LG[1<<N];
mint fac[100010]={1};

array<int,2> operator+(const array<int,2>&a0,const array<int,2>&a1){ return {a0[0]+a1[0],a0[1]+a1[1]}; }
int main(){
  rep(i,0,N) LG[1<<i]=i;
  rep(i,1,100000+1) fac[i]=fac[i-1]*i;
  int n=read();
  int m=read();
  rep(i,0,m) rb[1<<(read()-1)][0]++;
  rep(i,0,m) rb[1<<(read()-1)][1]++;
  rep(msk,1,1<<n) rbm[msk] = rbm[msk&(msk-1)] + rb[msk&-msk]; // 统计msk 红蓝
  rep(msk,1,1<<n) g[msk] = rbm[msk][0]==rbm[msk][1]?fac[rbm[msk][0]]:0; // 红==蓝，则 红!
  rep(msk,1,1<<n) {
    f[msk] = g[msk];
    // submsk != msk, submsk \subset msk, submsk 包含msk最低位, submsk + revsubmsk = msk
    int lowbit = msk&-msk;
    int highbits = msk-lowbit;
    if(highbits) for(int revsubmsk=highbits;revsubmsk != 0;revsubmsk=(revsubmsk-1)&highbits){
      f[msk] -= f[lowbit + (highbits-revsubmsk)]*g[revsubmsk];
    }
  }
  rep(msk,1,1<<n){
    int lowbit = msk&-msk;
    int highbits = msk-lowbit;
    for(int revsubmsk=highbits;;revsubmsk=(revsubmsk-1)&highbits){
      ans[msk] += f[lowbit + (highbits-revsubmsk)]*(ans[revsubmsk] + g[revsubmsk]);
      if(revsubmsk==0)break;
    }
  }
  printf("%d\n",(ans[(1<<n)-1]*fac[m].inv()).val());
  return 0;
}

// n个part
// m 红终端, i -> ri part
// m 蓝终端, i -> bi part
// m cables 连接 红<->蓝
// 同一个part可以连多个终端
// 每个终端只能一条cable, 所以一共m!方案连接cable
// s = 连接方案中连通块 块的个数
// 求 exp(s)
//
// 简化
// n个part点, n 17
// m 1e5
// m个左侧点
// m个右侧点
// 给定 每个单侧点 连接了一个part点
// 每个左侧点连接了一个右侧点,每个右侧点连接了一个左侧点

// f[mask] = mask内连成一个连通块 且无剩余蓝红的方案数
// g[mask] = mask内无剩余蓝红的方案数
// ans[s] = sum s的所有方案的连通块个数
// ans[s] = for mask, mask 包含最小点
// 		f[mask] * ans[s-mask] 两边互不影响计算右边
// 		+ 1 * g[mask] 计算左边
//
// g[mask] = sum红! , 满足sum红==sum蓝
// f[mask] = g[mask] - sum f[submask]*g[mask-submask], submask包含mask中最小的

Submission Info

Compile Error

Main.cpp: In function ‘ll read()’:
Main.cpp:8:21: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
    8 | ll read(){ll r;scanf("%lld",&r);return r;}
      |                ~~~~~^~~~~~~~~~~

Judge Result