Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
以下の条件を全て満たす頂点に 1 から N までの番号がついた N 頂点の有向グラフ G を考えます。
-
G はトーナメントである。すなわち、G に多重辺や自己ループはなく、G のどの 2 頂点 u,v に対しても、u \rightarrow v 辺または v \rightarrow u 辺のうちちょうど片方が存在する。
-
G の辺のうち、頂点番号が小さい方から大きい方へ向けられた辺はちょうど M 本存在する。
そのような有向グラフ G 全てに対する強連結成分の個数の総和を 998244353 で割ったあまりを求めてください。
制約
- 1 \le N \le 30
- 0 \le M \le \frac{N(N-1)}{2}
入力
入力は以下の形式で標準入力から与えられる。
N M
出力
答えを出力せよ。
入力例 1
3 1
出力例 1
7
条件を満たす有向グラフ G は以下の 3 個です。それぞれ強連結成分の個数は 3,1,3 であるため答えは 7 です。
入力例 2
6 2
出力例 2
300
入力例 3
25 156
出力例 3
902739687
Score : 700 points
Problem Statement
Consider a directed graph G with N vertices numbered 1 to N that satisfies all of the following conditions.
-
G is a tournament. In other words, G has no multi-edges or self-loops, and for any two vertices u,v of G, exactly one of the edges u \rightarrow v and v \rightarrow u exists.
-
Among the edges of G, exactly M are directed from a vertex with a smaller number to a vertex with a larger number.
Find the total number of strongly connected components over all such directed graphs G, modulo 998244353.
Constraints
- 1 \le N \le 30
- 0 \le M \le \frac{N(N-1)}{2}
Input
The input is given from Standard Input in the following format:
N M
Output
Print the answer.
Sample Input 1
3 1
Sample Output 1
7
Below are the three directed graphs G that satisfy the conditions. The numbers of their strongly connected components are 3,1,3 from left to right, so the answer is 7.
Sample Input 2
6 2
Sample Output 2
300
Sample Input 3
25 156
Sample Output 3
902739687