C++14(g++5.4) 解法, 执行用时: 3679ms, 内存消耗: 41568K, 提交时间: 2018-08-02 16:48:18

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long li;

const int mod = 998244353;
const li mod2 = (li)mod * mod;

inline int Add(int x) { return x >= mod ? x - mod : x; }
inline int Sub(int x) { return x < 0 ? x + mod : x; }
inline int Mul(int x, int y) { return (li)x * y % mod; }
void Add(int &x, int y) { x += y; if (x >= mod) x -= mod; }
void Sub(int &x, int y) { x -= y; if (x < 0) x += mod; }

int Pow(int x, int y) {
  int z = 1;
  for (; y; y >>= 1) {
    if (y & 1) z = Mul(z, x);
    x = Mul(x, x);
  }
  return z;
}

const int maxn = 19;
int n, m, all, g[maxn][maxn];

int ans[maxn + 1];
int stir[maxn + 1][maxn + 1];

int prod[maxn + 1];
int f[1 << maxn][maxn + 1];
li tmp[maxn + 1];

void AddPoly(int *a, int *b, int n) {
  for (int i = 0; i <= n; ++i) {
    Add(a[i], b[i]);
  }
}

void MulPoly(int *a, int *b, int n, int m) {
  fill(tmp, tmp + n + 1, 0);
  for (int j = 0; j <= m; ++j) {
    for (int i = 0; i + j <= n; ++i) {
      tmp[i + j] += (li)a[i] * b[j];
      if (tmp[i + j] >= mod2) tmp[i + j] -= mod2;
    }
  }
  for (int i = 0; i <= n; ++i) {
    a[i] = tmp[i] % mod;
  }
}

void Main(void) {
  for (int s = 0; s < 1 << n; ++s) {
    int m = __builtin_popcount(s), cnt = 0;
    for (int i = 0; i < n; ++i) {
      for (int j = i + 1; j < n; ++j) {
        if ((s >> i & 1) && (s >> j & 1) && g[i][j]) {
          ++cnt;
        }
      }
    }
    f[s][m] = Pow(2, cnt);
  }
  f[0][0] = 0;
  for (int i = 0; i < n; ++i) {
    for (int s = 0; s < 1 << n; ++s) {
      if (~s >> i & 1) {
        AddPoly(f[s | 1 << i], f[s], n);
      }
    }
  }
  for (int s = 0; s < 1 << n; ++s) {
    int m = __builtin_popcount(s);
    fill(prod, prod + n + 1, 0);
    prod[0] = 1;
    int coeff = (n - m) & 1 ? mod - 1 : 1;
    for (int i = 1; i <= n; ++i) {
      MulPoly(prod, f[s], n, m);
      Add(ans[i], Mul(coeff, prod[n]));
    }
  }
}

void Init(void) {
  for (int i = 0; i <= n; ++i) {
    stir[i][0] = i == 0;
    for (int j = 1; j <= i; ++j) {
      stir[i][j] = Add(stir[i - 1][j - 1] + Mul(stir[i - 1][j], j));
    }
  }
}

int main(void) {
  scanf("%d%d", &n, &m);
  all = (1 << n) - 1;
  for (int i = 0; i < m; ++i) {
    int a, b;
    scanf("%d%d", &a, &b);
    --a; --b;
    g[a][b] = g[b][a] = 1;
  }
  Main();
  Init();
  for (int i = 1, t = 1; i <= n; ++i) {
    t = Mul(t, i);
    ans[i] = Mul(ans[i], Pow(t, mod - 2));
  }
  for (int i = n; i >= 1; --i) {
    for (int j = i + 1; j <= n; ++j) {
      Sub(ans[i], Mul(ans[j], stir[j][i]));
    }
  }
  int sum = 0;
  for (int i = 1; i <= n; ++i) {
    Add(sum, Mul(Pow(i, i - 1), ans[i]));
  }
  printf("%d\n", sum);
  return 0;
}

C++ 解法, 执行用时: 3342ms, 内存消耗: 51808K, 提交时间: 2021-10-05 16:11:36

#include<bits/stdc++.h>
#define rep(i,x,y) for(int i=x; i<=y; ++i)
#define repd(i,x,y) for(int i=x; i>=y; --i)

using namespace std;
const int N=25,mod=998244353;
typedef long long LL;
const LL mod2=(LL)mod*mod;
int n,m,g[N][N],ans[N],st[N][N],p[N],f[1<<20][N],Ans;
LL tmp[N];

inline int add(int x) {return x>=mod?x-=mod:x;}
inline int sub(int x) {return x<0?x+mod:x;}
inline int mul(int x,int y) {return (LL)x*y%mod;}
void add(int &x,int y) {if((x+=y)>=mod) x-=mod;}
void sub(int &x,int y) {if((x-=y)<0) x+=mod;}

int getmi(int a,int x)
{
	int rt=1;
	while(x)
	{
		if(x&1) rt=mul(rt,a);
		a=mul(a,a),x>>=1;
	}
	return rt;
}

void addpoly(int a[],int b[],int n) {rep(i,0,n) add(a[i],b[i]);}

void mulpoly(int a[],int b[],int n,int m)
{
	fill(tmp,tmp+n+1,0);
	rep(j,0,m) rep(i,0,n)
	{
		tmp[i+j]+=(LL)a[i]*b[j];
		if(tmp[i+j]>=mod2) tmp[i+j]-=mod2;
	}
	rep(i,0,n) a[i]=tmp[i]%mod;
}

void solve()
{
	rep(s,0,(1<<n)-1)
	{
		int m=__builtin_popcount(s),cnt=0;
		rep(i,0,n-1)
			rep(j,i+1,n-1)
				if((s>>i&1) && (s>>j&1) && g[i][j])
					++cnt;
		f[s][m]=getmi(2,cnt);
	}
	f[0][0]=0;
	rep(i,0,n-1)
		rep(s,0,(1<<n)-1)
			if(~s>>i&1)
				addpoly(f[s|1<<i],f[s],n);
	rep(s,0,(1<<n)-1)
	{
		int m=__builtin_popcount(s);
		fill(p,p+n+1,0);
		p[0]=1;
		int c=(n-m)&1?mod-1:1;
		rep(i,1,n)
		{
			mulpoly(p,f[s],n,m);
			add(ans[i],mul(c,p[n]));
		}
	}
}

void init()
{
	rep(i,0,n)
	{
		st[i][0]=(i==0);
		rep(j,1,i)
			st[i][j]=add(st[i-1][j-1]+mul(st[i-1][j],j));
	}
}
	
int main()
{
	scanf("%d%d",&n,&m);
	rep(i,1,m)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		--u,--v,g[u][v]=g[v][u]=1;
	}
	solve();
	init();
	int t=1;
	rep(i,1,n)
		t=mul(t,i),ans[i]=mul(ans[i],getmi(t,mod-2));
	repd(i,n,1)
		rep(j,i+1,n)
			sub(ans[i],mul(ans[j],st[j][i]));
	rep(i,1,n) add(Ans,mul(getmi(i,i-1),ans[i]));
	printf("%d\n",Ans);
	return 0;
}