#1891. 乘积的期望

    ID: 1891 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1876来源:qoj.ac数据:公开样例数学

乘积的期望

乘积的期望

题目描述

第一试乘积的期望(expectation) IOI2025 中国国家集训队集中培训 乘积的期望(expectation) 【题目描述】 有一个长度为n 的序列a1, a2, · · · , an。初始序列的所有元素均为0。再给定正整数 m、c 和(n −m + 1) 个正整数b1, b2, · · · , bn−m+1。 对序列a1, a2, · · · , an 进行c 次操作,每次操作为: • 随机选择整数1 ≤x ≤n −m + 1,其中选到y(1 ≤y ≤n −m + 1) 的概率为 bi。将ax, ax+1, · · · , ax+m−1 增加1。 by !n−m+1 i=1 c 次操作中对x 的随机是独立的。 求操作完成后序列中所有元素的乘积的期望。为了避免浮点数输出,你需要将答案 对998244353 取模。 【输入格式】 从标准输入读入数据。 第一行三个整数n, m, c,分别表示序列长度、操作区间长度和操作次数。 第二行n −m + 1 个整数b1, · · · , bn−m+1,描述随机的权重。 【输出格式】 输出到标准输出。 输出一行一个整数,表示c 次操作后序列中所有数的乘积的期望。 【样例1 输入】 3 2 2 1 1 1 2 【样例1 输出】 1 1 【样例1 解释】 当两次操作选择的x 不同时,最终序列为1 2 1,序列元素乘积为2;否则序列为 2 2 0 或0 2 2,序列元素乘积均为0。两次操作选择的x 不同的概率为1 2,因此输出 2 × 1 2 = 1。 第2 页 共10 页 第一试乘积的期望(expectation) IOI2025 中国国家集训队集中培训 【样例2 输入】 10 3 10 1 1 2 3 4 5 6 7 8 2 【样例2 输出】 721023399 1 【样例3 输入】 20 12 98765 1 9 8 7 6 5 4 3 2 1 2 【样例3 输出】 560770686 1 【子任务】 对于所有测试数据,2 ≤m ≤n ≤50,1 ≤c < 998244353,对于1 ≤i ≤n −m + 1, 1 ≤bi ≤105。 Subtask 1(10%) : m ≤8。 Subtask 2(20%) : m ≤16。 Subtask 3(15%) : n ≤20, c ≤n。 Subtask 4(15%) : n ≤30, c ≤n。 Subtask 5(15%) : n ≤40, c ≤n。 Subtask 6(15%) : c ≤n。 Subtask 7(10%) : 无特殊限制。 第3 页 共10 页

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

3 2 2
1 1
1

样例 2

10 3 10
1 2 3 4 5 6 7 8
721023399