SS241121B. Soso 的模法矩阵（modmat）

题意

给你长度为 \(n\) 的 \(\{ a_i \}\)，长度为 \(m\) 的 \(\{ b_i \}\)，设 \(a_i' = \prod_{j=1}^i a_i,b_i' = \prod_{j=1}^i b_i\)，对所有 \(i \in [1,n],j\in [1,m]\)，求

然后以某种方式输出答案。\(n,m \le 5000, a_i,b_i \le 10^9\)。

思路

这个取模就非常恶心。

往变进制数方面去想，把 \(a_i'\) 表示成第 \(0\) 位满 \(b_1\) 进 \(1\)，第 \(1\) 位满 \(b_2\) 进一……，第 \(m-1\) 位满 \(b_m\) 进 \(1\)。第 \(i\) 位表示成 \(c_i\)，第 \(i\) 位上面填写 \(c_i\) 相当于十进制数字 \(c_i \times b_i'\)。

因为第 \(m\) 位填什么东西，取模后一定都没有了，因此不需要考虑第 \(m\) 位。

然后 \(a_i' \bmod b_j'\) 就等于 \(\sum_{k=0}^{j-1} c_k \times b_k' (\bmod \ 998244353)\)。

当 \(i\gets i+1\) 的时候，相当于乘上 \(a_{i+1}\)，变进制数乘法，每个 \(c_i\) 乘上 \(a_{i+1}\) 然后进位即可。

时间复杂度 \(O(nm)\)。代码应该很好写的。

思维好题，码量小。

code

雀食不难写。

#include<bits/stdc++.h>
#define sf scanf
#define pf printf
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
typedef long long ll;
namespace Resonance {
    constexpr int N=5e3+7,mod1=998244353,mod2=1e9+7;
    ll add(ll a,ll b) { return a+b>=mod1 ? a+b-mod1 : a+b; }
    ll add2(ll a,ll b) { return a+b>=mod2 ? a+b-mod2 : a+b; }
    void _add(ll &a,ll b) { a=add(a,b);}
    int n,m;
    int a[N],b[N];
    ll c[N];
    void main() {
        sf("%d%d",&n,&m);
        rep(i,1,n) sf("%d",&a[i]);
        rep(i,1,m) sf("%d",&b[i]);
        c[1]=1;
        rep(i,1,n) {
            ll tmp=0,s=0,p=1;
            ll ans=0;
            rep(j,1,m) {
                c[j]=c[j]*a[i]+tmp;
                tmp=c[j]/b[j];
                c[j]%=b[j];
                _add(s,p*c[j]%mod1);
                p=p*b[j]%mod1;
                ans=add2(ans*mod1%mod2,s);
            }
            pf("%lld\n",ans);
        }
    }
}
int main() {
    #ifdef LOCAL
    freopen("my.out","w",stdout);
    #else 
    freopen("modmat.in","r",stdin);
    freopen("modmat.out","w",stdout);
    #endif
    Resonance :: main();
}