407734: GYM102888 I 随机游走

Memory Limit:512 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

I. 随机游走time limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

对任意的两个正整数 n, m,定义 Kn, m 是满足下述条件的无向图:

  • Kn, m 中有 n + m 个点,标号分别为 1, 2, ..., n + m
  • 对点 1, 2, ..., n 中的每一个点 u,它与点 1, 2, ..., n 之间没有边,与点 n + 1, n + 2, ..., n + m 之间各有一条边。

为了方便说明,下图展示了 K2, 3 中所有节点的连接状态:

现在,你需要在 Kn, m 上按以下方式进行随机游走:

  1. 等概率地从所有点中选择一个点 s 作为起点。在 0 时刻,你位于点 s
  2. 若在 t 时刻,你位于点 u,则你可以在该时刻等概率地选择一个与 u 相邻的节点 v,并在 t + 1 时刻到达 v
  3. 若在 T 时刻,Kn, m 上所有的点都至少被到达了一次,则在该时刻停止随机游走过程。

请你编写一个程序,计算停止时刻 T 的数学期望 E(T) 在模 998, 244, 353 意义下的值。具体地说,设 M = 998, 244, 353,可以证明答案一定可以被表示成一个既约分数 ,其中 p, q 均为整数且 。输出满足 0 ≤ x < Mx·q ≡ p ± od{M} 的整数 x

Input

一行用空格隔开的两个整数 n, m (1 ≤ n, m ≤ 1, 000),含义见题目描述。

Output

输出一行一个整数 E(T),表示随机游走过程停止时刻 T 的数学期望 E(T) 在模 998, 244, 353 意义下的值。

ExamplesInput
1 1
Output
1
Input
2 2
Output
6
Input
299 213
Output
24844103
Note

样例 1 中,K1, 1 如下图所示:

0 时刻,点 1 和点 2 都各有 的概率被选中作为起点,并沿着图中唯一的边在 1 时刻到达另一个点,同时停止随机游走过程,故

加入题单

上一题 下一题 算法标签: