TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P6428
  • 题目
  • P6428咱们去烧菜吧
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 1s,512m
    问题描述

    你有 \(m\) 种物品,第 \(i\) 种物品的大小为 \(a_i\),数量为 \(b_i\)\(b_i=0\) 表示有无限个)。
    你还有 \(n\) 个背包,体积分别为 $1$ 到 \(n\),现在你很想知道用这些物品填满某个背包的方案数。
    为了满足你的好奇心,你决定把填满每个背包的方案数都算一遍。
    因为你其实只是闲得无聊,所以你只想知道方案数对 $998244353$($7\times 17\times 2^{23}+1$,一个质数)取模后的值。

    输入格式

    第一行两个非负整数,分别表示 \(n,m\)
    以下 \(m\) 行,每行两个非负整数,分别表示 \(a_i,b_i\)

    输出格式

    输出 \(n\) 个非负整数表示答案。

    提示

    样例输入

    5 3
    1 0
    1 1
    3 2
    

    样例输出

    2
    2
    3
    4
    4
    

    样例解释

    拼出 $1$~$5$ 的方案分别如下:
    \(\{1_1\},\{1_2\}\)
    \(\{1_1,1_1\},\{1_1,1_2\}\)
    \(\{1_1,1_1,1_1\},\{1_1,1_1,1_2\},\{3\}\)
    \(\{1_1,1_1,1_1,1_1\},\{1_1,1_1,1_1,1_2\},\{1_1,3\},\{1_2,3\}\)
    \(\{1_1,1_1,1_1,1_1,1_1\},\{1_1,1_1,1_1,1_1,1_2\},\{1_1,1_1,3\},\{1_1,1_2,3\}\)

    \(0< n,m\le 10^5, 0\le a_i\le 110000,0\le b_i\le 10^6\)