Sultan Rage

Luogu

IDLGP8565

Time1000ms

Memory512MB

DifficultyP6

洛谷原创O2优化洛谷月赛

有一个数列 $\{a_n\}$ 满足对 $n > m$ 均有 $a_n=\sum\limits_{j=1}^m a_{n-j}$，并且 $a_1,a_2,\cdots,a_m$ 是输入中给出的正整数。 $q$ 次询问，每一次给出一个正整数 $x$，问有多少个不可重正整数集 $S$ 满足 $\sum\limits_{s\in S}a_s=x$。答案对质数 $998244353$ 取模。本题有多组数据。 ## Input **本题有多组数据。** 第一行一个整数 $T$ 表示数据组数。对于每一组数据：第一行两个整数 $m,q$。第二行 $m$ 个整数 $a_1,a_2,\cdots,a_m$。第三行 $q$ 个整数，每一个整数代表一次询问。 ## Output 对于每组询问输出一行表示答案。 [samples] ## Note 对于所有数据，$T=5$，$2 \le m \le 100$，$1 \le q,a_i \le 100$，$1 \le x \le 10^{18}$。 $$ \def\arraystretch{1.5} \begin{array}{c|c|c|c|c|c}\hline \textbf{测试点编号}&\bm{m\le}&\bm{q \le }&\bm{a_i \le }& \bm{x \le}&\bm{\textbf{特殊性质}}\cr\hline \textsf1\sim \sf2 & 8&8 & 8 & 100\cr\hline \sf3\sim 5 & 15& &15&10^3 \cr\hline \textsf6 & & & & 1 &\cr\hline \sf7\sim 11 & & 1& & & \textsf{A}\cr\hline \sf12\sim 16 & 2& & &\cr\hline \sf17\sim 20 & &\cr\hline \end{array} $$ $\textsf A$：$m=10$，且 $x$ 在所有可能的 $x$ 中随机生成。

Samples

Input #1

2
2 5
1 1
3 5 7 9 11
3 5
1 2 5
4 7 10 18 22

Output #1

API Response (JSON)

{
  "problem": {
    "name": "Sultan Rage",
    "description": {
      "content": "有一个数列 $\\{a_n\\}$ 满足对 $n > m$ 均有 $a_n=\\sum\\limits_{j=1}^m a_{n-j}$，并且 $a_1,a_2,\\cdots,a_m$ 是输入中给出的正整数。 $q$ 次询问，每一次给出一个正整数 $x$，问有多少个不可重正整数集 $S$ 满足 $\\sum\\limits_{s\\in S}a_s=x$。答案对质数 $998244353$ 取模。 本题有多",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8565"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "有一个数列 $\\{a_n\\}$ 满足对 $n > m$ 均有 $a_n=\\sum\\limits_{j=1}^m a_{n-j}$，并且 $a_1,a_2,\\cdots,a_m$ 是输入中给出的正整数。\n\n$q$ 次询问，每一次给出一个正整数 $x$，问有多少个不可重正整数集 $S$ 满足 $\\sum\\limits_{s\\in S}a_s=x$。答案对质数 $998244353$ 取模。\n\n本题有多...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments