#1686. 硬币游戏

    ID: 1686 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1037来源:qoj.ac数据:公开样例动态规划前缀和

硬币游戏

硬币游戏

题目描述

标题: 硬币游戏 - Problem - QOJ.ac

Statistics

The problem was used in the following contests:

小 A 现在有 n 个硬币排成一行,最开始都是正面朝下,并且从左到右依次编号为 1,2,3,⋯,n−1,n。

小 A 决定玩一个游戏:小 A 会先进行 k 次操作,每次选定两个正整数 s,t 满足 1≤s<t≤n 然后翻转 s 号和 t 号硬币。

在 k 次操作完成后,小 A 会选定一个值 p(0≤p≤n) 。我们假设左边 p 个硬币 (编号为 1∼p) 中朝上的硬币有 a 个,右边 n−p 个(编号为 p+1∼n) 中朝上的有 b 个。

除此之外,小A还有一个美观度函数 H ,以及两个常数 x,y 。

小 A 一局游戏的分数被定义为 val=xpyn−pH(a) 。现在小 A 想求出所有游戏的分数和。

当然如果仅仅是求出所有游戏的分数和有点太无趣了,因此小A还规定了 a,b 的具体值。我们定义 F(x,y) 为所有满足 a=x,b=y 的不同游戏的分数之和。两个游戏不同当且仅当某次操作的 (s,t) 不同或者最后选择的 p 不同。

小 A 并不仅仅满足于求出 F(x,y) 。他又突发奇想,给了两个数 ra,rb ,想让你求出 ansk=∑i=0raF(i,rb) ,其中 k 表示进行了 k 次操作。

小 A 除了是一个游戏爱好者之外,还是一个精益求精,奋发向上的人。因此他会要求你求出 ans0,ans1,ans2,⋯,ansm−1,ansm 。 答案对 998244353 取模。

输入格式

第一行六个自然数 n,x,y,ra,rb,m 。第二行 ra+1 个数,表示 H(0),H(1),H(2),…,H(ra−1),H(ra) 。

输出格式

一行 m+1 个数,表示答案。

样例数据

样例 1 输入

5 1 4 1 1 4
1919 810

样例 1 输出

0 1231200 7387200 78796800 768268800

样例 2 输入

100 2 3 10 20 20
1 2 3 4 5 6 7 8 9 10 11

样例 2 输出

0 0 0 0 0 0 0 0 0 0 809274050 933560834 648523677 685804365 288106207 428246395 643105965 610311779 424132536 354030387 477940535

子任务

对于所有数据,保证 0≤n,x,y,H(i)<998244353,0≤ra,rb,m≤105,ra+rb≤n,且 x,y>0。

子任务编号 特殊性质 分值 1 n,m≤5000 10 2 ra,rb,m≤5000 20 3 ra,rb,m≤5×104,性质 A 20 4 性质 A 10 5 ra,rb,m≤5×104 15 6 无 25

性质 A:H(x) 只有一个位置非零。

每个子任务可能会依赖数据范围为其子集的子任务。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

5 1 4 1 1 4
1919 810
0 1231200 7387200 78796800 768268800

样例 2

100 2 3 10 20 20
1 2 3 4 5 6 7 8 9 10 11
0 0 0 0 0 0 0 0 0 0 809274050 933560834 648523677 685804365 288106207 428246395 643105965 610311779 424132536 354030387 477940535