#P16256. [Noi2026赛前集训]poly生成函数

[Noi2026赛前集训]poly生成函数

题目描述

给定长度为 NN 的正整数序列

A=(A1,A2,…,AN)A=(A_1,A_2,\ldots,A_N)

以及正整数 SS 和 TT。

求满足以下所有条件的非负整数序列

(c1,c2,…,cN)(c_1,c_2,\ldots,c_N)

的个数,结果对 998244353998244353 取模:

c1+c2+⋯+cN=S,c_1+c_2+\cdots+c_N=S, A1c1+A2c2+⋯+ANcN=T.A_1c_1+A_2c_2+\cdots+A_Nc_N=T.

输入格式

第一行包含四个整数 C,N,S,TC,N,S,T,其中 CC 为子任务编号。

第二行包含 NN 个整数 A1,A2,…,ANA_1,A_2,\ldots,A_N。

输出格式

输出满足条件的序列个数,对 998244353998244353 取模。

样例 1

0 4 4 10
1 2 3 4
5

样例 2

0 4 6 12
2 3 4 1
7

数据范围

对于所有数据:

1≤N≤20,1\le N\le 20, 1≤S,T≤1018,1\le S,T\le 10^{18}, 1≤Ai≤200,1\le A_i\le 200, ∑i=1NAi≤200.\sum_{i=1}^{N}A_i\le 200.
子任务编号 S,T≤S,T\le 特殊性质 分值
11 10001000 无 3232
22 101810^{18} A
33 无 3636

特殊性质 A:Ai=1A_i=1 当且仅当 i=Ni=N。同时满足 T=2ST=2S 且 N≥2N\ge 2。