問題一覧 > 通常問題

No.2108 Red or Blue and Purple Tree

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 9
作問者 : SumitacchanSumitacchan / テスター : 👑 hitonanodehitonanode 👑 ygussanyygussany
2 ProblemId : 8475 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-10-08 11:14:22

問題文

$N$ 頂点からなる完全グラフがあります。
このグラフの $M=N(N-1)/2$ 本の辺は $i=1,2,\dots,M$ と番号付けられ、互いに区別されます。

最初、$M$ 本の辺は全て白色です。
あなたは $M$ 本の辺の中から一部を選び、それぞれ赤・青・紫のいずれかの色で塗ります( $1$ 本の辺を複数の色で塗ることはできません)。
次の条件を全て満たす塗り分け方は何通りあるでしょうか。

  • 赤・青・紫の辺の数はそれぞれ $N-1-K,N-1-K,K$ であり、残りの辺は白色のままである。
  • 赤または紫の $N-1$ 本の辺のみを残して得られるグラフは木である。
  • 青または紫の $N-1$ 本の辺のみを残して得られるグラフは木である。

なお、ある $2$ つの塗り分け方において色が異なる辺 $i\ (1\le i \le M)$ が $1$ 本以上存在するとき、それらの塗り分け方は異なるとみなします。
答えは非常に大きくなることがあるので、$998244353$ で割った余りを求めてください。

一つの入力につき、$T$ 個のテストケースに答えてください。

制約

  • $1 \le T \le 5\times 10^5$
  • $2 \le N \le 2000$
  • $0 \le K \le N-1$
  • 入力は全て整数である。

入力

まず $1$ 行目に、入力に含まれるテストケースの数 $T$ が与えられます。

$T$

その後、$T$ 行にわたって $T$ 個のテストケースが与えられます。各テストケースは次の形式で $1$ 行で与えられます。

$N\ \ K$

出力

$T$ 行出力してください。
$i$ 行目 $(1\le i \le T)$ には、$i$ 番目のテストケースに対する回答を出力してください。

サンプル

サンプル1
入力
12
2 0
2 1
3 0
3 1
3 2
4 0
4 1
4 2
4 3
10 9
314 159
1883 1014
出力
0
1
0
6
3
12
120
108
16
100000000
771532131
812345678

例えば $(N,K)=(3,1)$ のときは、$M=3$ 本の辺を $1$ 本ずつ赤・青・紫に塗れば良いです。そのような塗り分け方は $6$ 通りあります。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。