[ARC163D] Sum of SCC
题意翻译
考虑一张竞赛图 $G$,其中有 $N$ 个节点,节点编号为 $1,2,\dots,N$,且 $G$ 满足:
- 对于 $G$ 中的所有边 $u\to v$,恰好有 $M$ 条边满足 $u<v$。
设 $f(G)$ 表示图 $G$ 中的强连通分量数量。请你求出所有满足条件的 $G$ 的 $f(G)$ 之和。
答案对 $998244353$ 取模。
$1\le N\le30$,$0\le M\le\frac{N(N-1)}2$。
题目描述
[problemUrl]: https://atcoder.jp/contests/arc163/tasks/arc163_d
以下の条件を全て満たす頂点に $ 1 $ から $ N $ までの番号がついた $ N $ 頂点の有向グラフ $ G $ を考えます。
- $ G $ はトーナメントである。すなわち、$ G $ に多重辺や自己ループはなく、$ G $ のどの $ 2 $ 頂点 $ u,v $ に対しても、$ u\ \rightarrow\ v $ 辺または $ v\ \rightarrow\ u $ 辺のうちちょうど片方が存在する。
- $ G $ の辺のうち、頂点番号が小さい方から大きい方へ向けられた辺はちょうど $ M $ 本存在する。
そのような有向グラフ $ G $ 全てに対する強連結成分の個数の総和を $ 998244353 $ で割ったあまりを求めてください。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ N $ $ M $
输出格式
答えを出力せよ。
输入输出样例
输入样例 #1
3 1
输出样例 #1
7
输入样例 #2
6 2
输出样例 #2
300
输入样例 #3
25 156
输出样例 #3
902739687
说明
### 制約
- $ 1\ \le\ N\ \le\ 30 $
- $ 0\ \le\ M\ \le\ \frac{N(N-1)}{2} $
### Sample Explanation 1
条件を満たす有向グラフ $ G $ は以下の $ 3 $ 個です。それぞれ強連結成分の個数は $ 3,1,3 $ であるため答えは $ 7 $ です。 !\[\](https://img.atcoder.jp/arc163/ee8acabc2a7d48164b3cc568e88f0840.png)