AT_abc385_g.[ABC385G] Counting Buildings

省选/NOI-

通过率:0%

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

对于一个 (1,2,…,N)(1,2,\dots,N) 的排列 P=(P1,P2,…,PN)P=(P_1,P_2,\dots,P_N),定义整数 L(P)L(P) 和 R(P)R(P):

  • 考虑 NN 栋从左到右的建筑,其中第 ii 栋建筑的高度为 PiP_i。然后 L(P)L(P) 表示从最左边能看到的建筑的数量,R(P)R(P) 表示从最右边能看到的建筑的数量。
    更正式的说,L(P)L(P) 为满足对于所有 j<ij<i 都有 Pj<PiP_j<P_i 的 ii 的个数,R(P)R(P) 为满足对于所有 j>ij>i 都有 Pi>PjP_i>P_j 的 ii 的个数。

给定你整数 NN 和 KK。找出满足 L(P)−R(P)=KL(P)-R(P)=K 的 (1,2,…,N)(1,2,\dots,N) 的排列 PP 的数量对 998244353998244353 取模后的值。

输入格式

输入从标准输入中读入:

N K

输出格式

输出答案。

样例 1 解释

  • P=(1,2,3)P=(1,2,3): L(P)−R(P)=3−1=2L(P)-R(P)=3-1=2。
  • P=(1,3,2)P=(1,3,2): L(P)−R(P)=2−2=0L(P)-R(P)=2-2=0。
  • P=(2,1,3)P=(2,1,3): L(P)−R(P)=2−1=1L(P)-R(P)=2-1=1。
  • P=(2,3,1)P=(2,3,1): L(P)−R(P)=2−2=0L(P)-R(P)=2-2=0。
  • P=(3,1,2)P=(3,1,2): L(P)−R(P)=1−2=−1L(P)-R(P)=1-2=-1。
  • P=(3,2,1)P=(3,2,1): L(P)−R(P)=1−3=−2L(P)-R(P)=1-3=-2。

满足 L(P)−R(P)=KL(P)-R(P)=K 的排列 PP 的数量为 11。

样例 3 解释

输出个数对 998244353998244353 取模后的值。

输入输出样例

  • 输入#1

    3 -1

    输出#1

    1
  • 输入#2

    1 0

    输出#2

    1
  • 输入#3

    2024 385

    输出#3

    576300012

说明/提示

  • 1≤N≤2×1051\le N\le 2\times 10^5
  • ∣K∣≤N−1\mid K\mid\le N-1
  • 所有输入都为整数。

输入解题思路,AI测评打分。不知道怎么写?

首页