我们考虑维护一个变进制数 $C$，或者说维护数组 $c$ 满足：

$$
\prod_{i=0}^K a_i = \sum_{i=0}^m c_i \prod_{j=0}^i b_j
$$

即一个每一位进制不同的数。

那么 $\mod \sum_{i=0}^K b_i$ 的结果就是后 $K$ 位。

考虑上 $K$ 增加时如何维护新的 $c$，显然可以把 $c_i \to c_i \cdot a_K$，然后进位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=5000;
const int mod=1e9+7;
const int base=998244353;
int n,m;
int a[maxn+5],b[maxn+5];
ll c[maxn+5];
signed main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=m;i++) scanf("%d",&b[i]);
    c[1]=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++) c[j]*=a[i];
        for(int j=1;j<=m;j++)
            c[j+1]+=c[j]/b[j],c[j]%=b[j];
        ll res=0,sum=0,tmp=1;
        for(int j=1;j<=m;j++){
            sum=(sum+tmp*c[j])%base;
            res=(res*base+sum)%mod;
            tmp=(tmp*b[j])%base;
        }
        printf("%lld\n",res);
    }
    return 0;
}