#PQJ134x10374. QOJ 134_10374

    ID: 2593 传统题 2000ms 512MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:集训队互测 2018线性代数数学

QOJ 134_10374

标题: 小 H 爱染色 - Problem - QOJ.ac

#10374. 小 H 爱染色

Statistics

The problem was used in the following contests:

有排成一列的 n 个球,编号依次为 0 到 n−1 ,初始都为白色。小 H 会重复以下操作共 2 次:随机选择其中的 m 个球将它们染成黑色(可以重复染黑球)。小 H 对编号最小的黑球情有独钟,她想知道,如果令 A 为它的编号, F(A) 的期望是多少。其中, F(x) 为一个次数不超过 m 的多项式, F(A) 表示 x=A 时多项式的值。

输入格式

第一行两个整数 n,m 。

第二行 m+1 个整数,第 i 个整数为 F(i−1) 。

输出格式

一行一个整数,如果令 E 表示 F(A) 的期望,输出 E×(nm)2 模 998244353 的值。

样例数据

样例输入

8 5
45856608 386378255 106492167 28766400 272276589 93721672

样例输出

321347828

子任务

  • 对于 10% 的数据,n≤10,m≤5
  • 对于 20% 的数据,n≤100,m≤100
  • 对于 30% 的数据,n≤1000,m≤1000
  • 对于另外 5% 的数据,m≤1000000,且保证多项式 F(x)=1
  • 对于另外 5% 的数据,m≤5000,且保证多项式 F(x)=x
  • 对于另外 10% 的数据,m≤5000,且保证多项式 F(x)=xm
  • 对于 70% 的数据,m≤5000
  • 对于 80% 的数据,m≤20000
  • 对于 100% 的数据,n≤998244353,m≤1000000