#PQJ2880x16204. QOJ 2880_16204

    ID: 2882 传统题 1000ms 1024MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:SCOI 2024枚举数学

QOJ 2880_16204

CCF NOI 2024 四川省代表队评测活动 第二试 交换(swap) 交换(swap) 【题目描述】 给定 𝑛 个数字串,每个数字串只包含 0 到 9 的数字。现需要进行 𝑘 次交换操作,每次操 作在所有串的所有位置中任选两个不同位置交换。求交换操作后,对于所有可能,𝑛 个串转化 为整数的乘积的和。 注意:每次交换操作之间选择的位置互相独立,允许两次交换操作选择的两个位置完全相 同。 【输入格式】 从文件 swap.in 中读入数据。 输入的第一行包含两个整数 𝑛 和 𝑘。 接下来 𝑛 行,每行包含一个数字串 𝑠𝑖。保证字符串中只包含数字 0 到 9。 【输出格式】 输出到文件 swap.out 中。 输出一行一个整数,表示答案。由于答案很大,请输出答案对 109 + 7 取模后的值。 【样例1 输入】 1 2 1 2 12 3 34 【样例1 输出】 1 3740 【样例1 解释】 进行一次交换操作后,这两个串最终有 6 种可能情况:

  1. 21, 34
  2. 12, 43
  3. 32, 14
  4. 42, 31
  5. 13, 24 第2 页 共11 页

CCF NOI 2024 四川省代表队评测活动 第二试 交换(swap) 6. 14, 32 则最终答案为 21 ⋅34 + 12 ⋅43 + 32 ⋅14 + 42 ⋅31 + 13 ⋅24 + 14 ⋅32 = 3740 【样例2 输入】 1 2 2 2 1 3 12 【样例2 输出】 1 165 【样例2 解释】 进行两次交换操作后,这两个串最终有 9 种可能情况:

  1. 1, 12
  2. 2, 11
  3. 1, 21
  4. 1, 21
  5. 1, 12
  6. 2, 11
  7. 2, 11
  8. 1, 21
  9. 1, 12 则最终答案为 1 ⋅12 + 2 ⋅11 + 1 ⋅21 + 1 ⋅21 + 1 ⋅12 + 2 ⋅11 + 2 ⋅11 + 1 ⋅21 + 1 ⋅12 = 165 【样例3】 见选手目录下的 swap/swap3.in 与 swap/swap3.ans。 这个样例满足测试点 1 ∼2 的条件限制。 【样例4】 见选手目录下的 swap/swap4.in 与 swap/swap4.ans。 这个样例满足测试点 3 ∼5 的条件限制。 第3 页 共11 页

CCF NOI 2024 四川省代表队评测活动 第二试 交换(swap) 【样例5】 见选手目录下的 swap/swap5.in 与 swap/swap5.ans。 这个样例满足测试点 6 ∼8 的条件限制。 【样例6】 见选手目录下的 swap/swap6.in 与 swap/swap6.ans。 这个样例满足测试点 9 ∼10 的条件限制。 【样例7】 见选手目录下的 swap/swap7.in 与 swap/swap7.ans。 这个样例满足测试点 11 ∼12 的条件限制。 【样例8】 见选手目录下的 swap/swap8.in 与 swap/swap8.ans。 这个样例满足测试点 13 ∼18 的条件限制。 【数据范围】 对于所有测试数据保证:1 ≤𝑛≤100,1 ≤𝑘≤109,1 ≤|𝑠𝑖| ≤107,2 ≤∑|𝑠𝑖| ≤107。 测试点编号 𝑛 𝑘 |𝑠𝑖| ∑|𝑠𝑖| 特殊性质 1 ∼2 ≤5 ≤3 ≤5 ≤107 无 3 ∼5 = 1 ≤109 ≤107 6 ∼8 ≤100 = 1 9 ∼10 ≤2 ≤109 ≤107 11 ∼12 ≤100 A 13 ∼18 ≤105 ≤105 无 19 ∼20 ≤107 ≤107 特殊性质 A: 字符串只包含数字 1 和 2。 第4 页 共11 页