P4921 情侣?给我烧了!

    • 241通过
    • 636提交
  • 题目提供者 Imagine
  • 评测方式 云端评测
  • 标签
  • 难度 NOI/NOI+/CTSC
  • 时空限制 1000ms / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    有 $n$ 对情侣来到电影院观看电影。在电影院,恰好留有 $n$ 排座位,每排包含 $2$ 个座位,共 $2×n$ 个座位。

    现在,每个人将会随机坐在某一个位置上,且恰好将这 $2 × n$ 个座位坐满。

    如果一对情侣坐在了同一排的座位上,那么我们称这对情侣是和睦的。

    你的任务是求出当 $k = 0, 1, ... , n$ 时,共有多少种不同的就坐方案满足恰好有 $k$ 对情侣是和睦的。

    两种就坐方案不同当且仅当存在一个人在两种方案中坐在了不同的位置。不难发现,一共会有 $(2n)!$ 种不同的就坐方案。

    输入输出格式

    输入格式:

    输入包含多组数据。

    输入的第一行包含一个正整数 $T(1 \leq T \leq 1000)$,表示数据的组数。

    接下来 $T$ 行,每行包含一个正整数 $n(1 \leq n \leq 1000)$。

    输出格式:

    对于每组输入数据,输出共 $n + 1$ 行,每行包含 $1$ 个整数,分别表示 $k = 0, 1, ..., n$ 时满足恰好有 $k$ 对情侣是和睦的就坐方案数。由于结果可能较大,因此输出对 $998244353$ 取模的结果。

    输入输出样例

    输入样例#1: 复制
    2
    1
    2
    
    输出样例#1: 复制
    0
    2
    16
    0
    8
    

    说明

    本题只有一个$T=1000$的数据点。。。暴力还是算了吧!

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。