TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P5312
  • 题目
  • P5312「2018 集训队互测 Day 5」小 H 爱染色
    限制 : 时间限制 : 15000 MS   空间限制 : 524288 KB
    评测说明 : 3s
    问题描述

    有排成一列的 \(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\times C^{m}_{n}\times C^{m}_{n}\) 模 $998244353$ 的值。

    提示

    样例输入

    8 5  
    45856608 386378255 106492167 28766400 272276589 93721672
    

    样例输出

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

    来源  2s,512m