Submission #35519263

---

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/modint>
using mint = atcoder::modint998244353;
using namespace std;
#define rep(i,a,n) for(int i=a;i<(int)(n);i++)
#define per(i,a,n) for(int i=n;i-->(int)(a);)
int read(){int r;scanf("%d",&r);return r;}
template<class T>
T det(vector<vector<T>>& a){ // 高斯消元
  auto n=a.size();
  if(n==0)return 1;
  assert(n==a[0].size());
  T ans=1;
  T neg=-1; // 除法慢 少用除法
  rep(j,0,n){
    rep(i,j,n)if(a[i][j]!=0){ // >=j行中找j列首个非零值,做行交换
      if(i!=j){
        std::swap(a[i],a[j]);
        ans*=neg;
      }
      break;
    }
    ans*=a[j][j];// 主元
    if(ans==0)return 0;
    T t=T(1)/a[j][j]; // 少做除法
    rep(k,j,n)a[j][k]*=t;
    rep(i,j+1,n)per(k,j,n)a[i][k]-=a[i][j]*a[j][k]; // 行变换, 注意per顺序
  }
  return ans;
}

// Ex
const int N=14;
mint fac[N+1]={1};
mint f[1<<N];// f[mask]=mask中的点的生成树个数
mint g[1<<N][N]={{1}}; // g[0][0]=1; f[mask][i]=mask中的点选了i条边的森林个数
int c[1<<N];// bit count
int e[N][N];
int n;

int main(){
  n = read();
  rep(i,1,n+1)fac[i]=fac[i-1]*i;
  rep(S,1,1<<n)c[S]=c[S&(S-1)]+1;
  int m = read();
  rep(_,0,m){
    int u = read()-1;
    int v = read()-1;
    e[u][v]+=1;
    e[v][u]+=1;
  }
  // f
  rep(S,1,1<<n){
    auto A=vector(c[S]-1,vector<mint>(c[S]-1,0)); // 忽略第一行第一列
    int ni=-1;
    rep(i,0,n)if(S&(1<<i)){
      int nj=ni+1;
      rep(j,i+1,n)if(S&(1<<j)){
        int d=e[i][j];
        if(~ni)A[ni][ni]+=d;
        if(~nj)A[nj][nj]+=d;
        if(~ni&&~nj)A[ni][nj]=A[nj][ni]=-d;
        nj++;
      }
      ni++;
    }
    f[S]=det(A);
  }
  // g 子集遍历
  rep(S,1,1<<n)rep(i,0,c[S])for(int T=S;T;T=(T-1)&S)if(T&S&-S and i-(c[T]-1)>=0)g[S][i]+=f[T]*g[S-T][i-(c[T]-1)];
  rep(k,1,n)printf("%d\n",(g[(1<<n)-1][k]*fac[k]/mint(m).pow(k)).val());
  return 0;
}

Submission Info

Compile Error

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

Judge Result