F - Forbidden Tournament Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 2000 点

問題文

整数 N,K と素数 P が与えられます。N 頂点の有向グラフ G であって、以下を全て満たすものの個数を P で割った余りを求めてください。ただし、頂点どうしは互いに区別します。

  • G はトーナメントである。すなわち、G に多重辺や自己ループはなく、G のどの 2 点 u,v に対しても、u\to v 辺または v\to u 辺のうちちょうど片方が存在する。
  • G のどの頂点の入次数も K 以下である。
  • G のどの相異なる 4 頂点 a,b,c,d に対しても、a\to b, b\to c, c\to a, a\to d, b\to d, c\to d の 6 辺がすべて同時に存在することはない。

制約

  • 4 \leq N \leq 200
  • \frac{N-1}{2} \leq K \leq N-1
  • 10^8<P<10^9
  • N,K は整数である
  • P は素数である

入力

入力は以下の形式で標準入力から与えられる。

N K P

出力

条件を満たす有向グラフの個数を P で割った余りを出力せよ。

入力例 1

4 3 998244353

出力例 1

56

4 頂点のグラフ 64 個のうち、禁止された誘導部分グラフと同型である 8 個を除いた 56 個が条件を満たします。

入力例 2

7 3 998244353

出力例 2

720

入力例 3

50 37 998244353

出力例 3

495799508

Score : 2000 points

Problem Statement

Given are integers N and K, and a prime number P. Find the number, modulo P, of directed graphs G with N vertices that satisfy below. Here, the vertices are distinguishable from each other.

  • G is a tournament, that is, G contains no duplicated edges or self-loops, and exactly one of the edges u\to v and v\to u exists for any two vertices u and v.
  • The in-degree of every vertex in G is at most K.
  • For any four distinct vertices a, b, c, and d in G, it is not the case that all of the six edges a\to b, b\to c, c\to a, a\to d, b\to d, and c\to d exist simultaneously.

Constraints

  • 4 \leq N \leq 200
  • \frac{N-1}{2} \leq K \leq N-1
  • 10^8<P<10^9
  • N and K are integers.
  • P is a prime number.

Input

Input is given from Standard Input in the following format:

N K P

Output

Print the number of directed graphs that satisfy the conditions, modulo P.

Sample Input 1

4 3 998244353

Sample Output 1

56

Among the 64 graphs with four vertices, 8 are isomorphic to the forbidden induced subgraphs, and the other 56 satisfy the conditions.

Sample Input 2

7 3 998244353

Sample Output 2

720

Sample Input 3

50 37 998244353

Sample Output 3

495799508