TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P4864
  • Problem
  • P4864化学题
    Limits : Time Limit : 32500 MS   Memory Limit : - KB
    Judgment Tips : 2.5s 512M
    Description

    计算化学式为 \(\rm C_n H_{2n+2}\) 的烷烃的同分异构体个数。

    多组数据,答案对 $998244353$ 取模。

    Input Format

    第一行一个整数 \(T\),表示数据组数。

    接下来 \(T\) 行,每行一个整数 \(n\),表示询问化学式为 \(\rm C_n H_{2n+2}\) 的烷烃的同分异构体个数。

    Output Format

    共输出 \(T\) 行,每行一个整数,表示答案。

    Sample Input

    5
    3
    4
    5
    233
    666

    Sample Output

    1
    2
    3
    134793965
    35803200

    Hint
    测试点编号 \(T\) \(n\) 分值
    1 \(=1\) \(\leq 8\) $5$
    2 \(=1\) \(\leq 200\) $5$
    3 \(=1\) \(\leq 200\) $5$
    4 \(=1\) \(\leq 2000\) $5$
    5 \(=1\) \(\leq 2000\) $5$
    6 \(=1\) \(\leq 2000\) $5$
    7 \(=1\) \(= 66666\) $5$
    8 \(=1\) \(\leq 10^5\) $5$
    9 \(=1\) \(\leq 10^5\) $5$
    10 \(=1\) \(\leq 10^5\) $5$
    11 \(=1\) \(\leq 10^5\) $5$
    12 \(=1\) \(\leq 10^5\) $5$
    13 \(=10^5\) \(\leq 10^5\) $40$

    提示:如果你不知道什么是烷烃,那么你可以认为这个问题等价于求 \(n\) 个点的无标号无根树并满足每个点的度数 \(\leq 4\) 的树的个数。