TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • 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