No.1762 🐙🐄🌲
タグ : / 解いたユーザー数 10
作問者 :
NyaanNyaan
/ テスター :
tokusakurai
PCTprobability
Problem Statement
Nyaan, who loves polynomials, has decided to make polynomials by combining "octopuses" and "cows".
A tree satisfying the following conditions is called an octopus-cow tree with $N$ vertices.
- The vertices are numbered from $1$ to $N$, and each vertex has a picture of either an "octopus" or a "cow" drawn on it.
- The degree of a vertex with a picture of an "octopus" is $\mathbf{8}$ or less.
- The degree of a vertex with a picture of a "cow" is $\mathbf{4}$.
- Vertices with the same picture are not adjacent.
Also, among the vertices of an octopus-cow tree, a vertex with a picture of an "octopus" and degree $8$ is called a "perfect octopus".
You are given $N, P$. Find the number of octopus-cow trees with $N$ vertices that have exactly $P$ perfect octopuses, modulo $998244353$.
Constraints
- All inputs are integers.
- $2 \leq N \leq 5 \times 10^5$
- $0 \leq P \leq N$
Input
$N\ P$
Output
Print the answer in $1$ line.
Sample
Sample 1
Input
5 0
Output
5
With $5$ vertices and no perfect octopus, there is only the following $1$ shape of unlabeled octopus-cow tree, and there are $5$ ways to assign the labels.
Sample 2
Input
13 0
Output
48048000
With $13$ vertices and no perfect octopus, there are the following $2$ shapes of unlabeled octopus-cow trees.
The numbers of ways to assign the labels are $\frac{13!}{144}$ and $\frac{13!}{1296}$ respectively, for a total of $\frac{13! \cdot 10}{1296} = 48048000$ ways.
Sample 3
Input
133333 1333
Output
425602496
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。