No.1762 🐙🐄🌲
タグ : / 解いたユーザー数 7
作問者 :
NyaanNyaan
/ テスター :
tokusakurai
PCTprobability
問題文
多項式が大好きな Nyaan さんは「タコ」と「うし」を組み合わせて多項式を作ることにしました。
次の条件を満たす木を $N$ 頂点のタコうし木と呼びます。
- 頂点にはそれぞれ $1$ から $N$ までの番号が振られていて、各頂点には「タコ」か「うし」のいずれかの絵が書かれている。
- 「タコ」の絵が描かれた頂点の次数は $\mathbf{8}$ 以下である。
- 「うし」の絵が描かれた頂点の次数は $\mathbf{4}$ である。
- 同じ絵が描かれた頂点は隣接しない。
また、タコうし木の頂点のうち、「タコ」の絵が描かれた次数が $8$ である頂点のことを "完全なタコ" と呼びます。
$N, P$ が与えられます。完全なタコをちょうど $P$ 個持つ $N$ 頂点のタコうし木の個数を $998244353$ で割ったあまりを求めてください。
制約
- 入力は全て整数である。
- $2 \leq N \leq 5 \times 10^5$
- $0 \leq P \leq N$
入力
$N\ P$
出力
答えを $1$ 行に出力してください。
サンプル
サンプル1
入力
5 0
出力
5
頂点数 $5$ で完全なタコが存在しない頂点ラベルなしタコうし木の形は次の $1$ 通りのみで、ラベルのつけ方は $5$ 通りあります。
サンプル2
入力
13 0
出力
48048000
頂点数 $13$ で完全なタコが存在しない頂点ラベルなしタコうし木の形は次の $2$ 通りです。
頂点ラベルのつけ方はそれぞれ $\frac{13!}{144}$ 通り、 $\frac{13!}{1296}$ 通りで、合計 $\frac{13! \cdot 10}{1296} = 48048000$ 通りになります。
サンプル3
入力
133333 1333
出力
425602496
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。