题解：AT_abc436_g [ABC436G] Linear Inequation

本题是一个完全背包问题。设 \(A=\max_{i=1}^nA_i\)。

设 \(f(m)\) 表示 \(\sum_{i=1}^NA_ix_i=m\) 的解数，考虑写出生成函数：

\[F(z)=\prod_{i=1}^N\sum_{k=0}^{+\infty}z^{A_ik}=\prod_{i=1}^N\frac{1}{1-z^{A_i}} \]

则 \(f(m)=[z^m]F(z)\)。

由于 \(F(z)\prod_{i=1}^N(1-z^{A_i})=1\)，故 \(f(m)\) 是一个阶数最多为 \(D=\sum_{i=1}^NA_i\le NA\le 10^4\) 的线性递推。答案是 \(\sum_{m=1}^Mf(m)\)，从而是一个阶数最多为 \(D+1\) 的线性递推。

通过上面的分析，你当然可以直接把线性递推系数算出来。但是我懒，所以通过完全背包求出前充分多项的值后，直接用 Berlekamp-Massey 算法求线性递推系数即可。

最后使用 Bostan-Mori 或其他算法求解线性递推即可。

时间复杂度 \(O(D^2+D\log D\log M)\)，其中 \(D=NA\)。

代码：

//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x, y, z) for(int x = (y); x <= (z); ++x)
#define per(x, y, z) for(int x = (y); x >= (z); --x)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do {freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);} while(false)
#define endl '\n'
using namespace std;
typedef long long ll;namespace Polynomial {// 篇幅过长，多项式全家桶省略// 完整代码见 https://atcoder.jp/contests/abc436/submissions/71684486
}using namespace Polynomial;const int K = 105, M = 2e4 + 5;int n, a[K];
ll m;int main() {ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);initPoly(N);cin >> n >> m;rep(i, 1, n) cin >> a[i];Poly<mod, g> F(M);F[0] = 1;rep(i, 1, n) rep(j, a[i], M - 1) F[j] += F[j - a[i]];rep(j, 1, M - 1) F[j] += F[j - 1];if(m < M) cout << F[m] << endl;else {Poly<mod, g> A = berlekamp_massey(F);A.insert(A.begin(), 0);cout << bostan_mori(A, F, m, A.size()) << endl;}return 0;
}