题目详情题解（0）讨论（0）提交记录（0）

AT_abc425_e.[ABC425E] Count Sequences 2

普及+/提高

通过率：0%

AC君温馨提醒

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

题目描述

给定一个正整数 NN 和一个长度为 NN 的正整数序列 C=(C1,C2,…,CN)C=(C_1, C_2, \ldots, C_N)。

请你对于每组测试数据（共 TT 组），求满足以下条件的正整数序列的数量，并对给定正整数 MM 取模后输出：

  • 序列中所有元素都在 11 到 NN 之间（包含 11 和 NN）。
  • 对于每个 i=1,2,…,Ni=1,2,\ldots,N，数 ii 在序列中恰好出现 CiC_i 次。

TT 组测试数据共用同一个 MM。请分别输出每组测试数据的答案。

输入格式

输入通过标准输入给出，格式如下：

TT MM
case1\mathrm{case}_1
case2\mathrm{case}_2
⋮\vdots
caseT\mathrm{case}_T

第 ii 组测试数据，casei\mathrm{case}_i，格式如下：

NN C1C_1 C2C_2 …\ldots CNC_N

输出格式

输出 TT 行，每行一个答案。第 ii 行输出第 ii 组测试数据的答案。

输入输出样例

  • 输入#1

    3 1000000000
2
2 2
5
1 1 1 1 1
6
1 2 3 4 5 6

    输出#1

    6
120
230379200

  • 输入#2

    3 998244353
1
1
3
4 2 5
10
500 500 500 500 500 500 500 500 500 500

    输出#2

    1
6930
261233246

说明/提示

样例解释 1

对于第一组测试数据，满足条件的序列有 (1,1,2,2)(1,1,2,2)、(1,2,1,2)(1,2,1,2)、(1,2,2,1)(1,2,2,1)、(2,1,1,2)(2,1,1,2)、(2,1,2,1)(2,1,2,1)、(2,2,1,1)(2,2,1,1)，共 6 个序列。

数据范围

  • 1≤T≤1051 \leq T \leq 10^5
  • 2≤M≤1092 \leq M \leq 10^9
  • 1≤N1 \leq N
  • 1≤Ci1 \leq C_i
  • ∑i=1NCi≤5000\sum_{i=1}^N C_i \leq 5000
  • 所有测试数据中 NN 的总和不超过 3×1053\times 10^5
  • 所有输入均为整数。

由 ChatGPT 5 翻译

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

首页