Submission #49891988

---

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++)
#define per(i,a,n) for (ll i=n;i-->(ll)(a);)
ll read(){ll r;scanf("%lld",&r);return r;}
const int N=30;
const int MXEDGE=225; // 最大边数
mint h[N+1][N+1][MXEDGE+1]; // h[有序0个数][有序1个数][无重边数]=全连通方案数
mint f[N+1][MXEDGE+1]; // f[有序点数][边数] = 合法全通方案数
mint g[N+1][MXEDGE+1]; // g[有序点数][边数] = 合法方案数
mint p[MXEDGE+1]; // p[c] = m个有序点 上色c种，每种颜色至少一个点的方案数
mint fac[MXEDGE+10]={1};
mint ifac[MXEDGE+10]={1};
mint binom(int n,int m){return (m>n or m<0)?0:(fac[n]*ifac[m]*ifac[n-m]);}
int main(){
  rep(i,1,MXEDGE+1) fac[i]=fac[i-1]*i;
  ifac[MXEDGE]=fac[MXEDGE].inv();
  per(i,0,MXEDGE) ifac[i]=ifac[i+1]*(i+1);
  int n=read();
  int m=read();
  rep(i,1,N+1) rep(j,0,N+1-i) rep(c,0,i*j+1){
    h[i][j][c] = binom(i*j,c); // 不重复任意连c条
    rep(i0,1,i+1) rep(j0,0,j+1) if(i0+j0 != i+j) rep(c0,0,min(i0*j0,c)+1) { // 与最小i相连的连通块
      h[i][j][c] -= h[i0][j0][c0]*binom(i-1,i0-1)*binom(j,j0)*binom((i-i0)*(j-j0),c-c0);
    }
  }
  // 没加-fsanitize 1.2s
  // 加了-fsanitize 9s
  rep(i,1,N+1) rep(j,0,MXEDGE+1) rep(t,1,i+1) f[i][j] += binom(i-1,t-1) * h[t][i-t][j];
  g[0][0] = 1;
  rep(i,1,N+1) rep(j,0,MXEDGE+1) rep(t,1,i+1) rep(k,0,j+1) g[i][j] += binom(i-1,t-1)*f[t][k]*g[i-t][j-k];
  vector<mint> impwr(MXEDGE+1);
  rep(i,0,MXEDGE+1) impwr[i] = mint(i).pow(m);
  rep(c,1,MXEDGE+1) rep(i,0,c+1) p[c] += binom(c,i) * impwr[i] * ((c-i)%2==0?1:-1);
  mint ans =0;
  rep(c,0,MXEDGE+1) ans += g[n][c]*p[c];
  printf("%d\n",(ans*mint(2).pow(m)).val());
  return 0;
}

Submission Info

Compile Error

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

Judge Result