← 返回题目列表

AtCoder · arc133_e

E. 循环中位数

中文机器翻译题面 查看原题

分数: 800 点

问题陈述

给定的是整数 N, M, V,和 A。 考虑以下过程。

  • 选择一个序列 N 之间的整数 1 和 V (含): x=(x_1,x_2,\cdots,x_N).
  • 选择一个序列 M 之间的整数 1 和 V (含): y=(y_1,y_2,\cdots,y_M).
  • 让 a 是一个变量并初始化它 a=A.
  • 对于每个 i=0,1,\cdots,N \times M-1,执行以下操作。
    • 替换值 a 中位数为 a,x_{(i \bmod N)+1},y_{(i \bmod M)+1}.
  • 打印最终值 a.

考虑对每对可能的序列执行此过程 x,y。求将要打印的值的总和,模数 998244353.

约束

  • 1 \leq N,M \leq 200000
  • 1 \leq A \leq V \leq 200000
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N M V A

输出

打印答案。


样本输入 1

2 1 2 1

示例输出 1

11

例如,当 x=(1,2),y=(2),程序如下。

  • 初始化 a 与 a=1.
  • 对于 i=1:替换值 a 中位数为 a(=1),x_1(=1),y_1(=2),即 1.
  • 对于 i=2:替换值 a 中位数为 a(=1),x_2(=2),y_1(=2),即 2.
  • 打印 a(=2).

有以下三种情况: 将打印 2 : (x=(1,2),y=(2)), (x=(2,1),y=(2)), (x=(2,2),y=(2))。在其他五起案件中, 将打印 1 。 因此,答案是 2 \times 3 + 1\times 5=11.


示例输入 2

2 2 5 4

示例输出 2

2019

示例输入 3

2100 2300 2201 2022

示例输出 3

407723438