CF1218E Product Tuples

Tx_Lcy · 2023-01-03 12:50:23 · 题解

题目传送门

思路

真就暴力出奇迹了。

设 f_{i,j} 表示前 i 个数，选 j 个数乘起来的乘积和。

转移 f_{i,j}=f_{i-1,j}+f_{i-1,j-1} \times b_i。

然后，就没有然后了，滚存一下，本来想交个暴力然后优化的，结果直接过了。

复杂度 \mathcal O(Qn^2)。

码

//A tree without skin will surely die.
//A man without face is invincible.
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define sqr(x) ((x)*(x))
#define all(x) (x).begin(),(x).end()
#define Tim ((double)clock()/CLOCKS_PER_SEC)
#define mid ((l+r)>>1)
#define lowbit(x) (x&-x)
int const N=2e4+10;
int const mod=998244353;
int a[N],b[N],n,k,f[2][N];
inline int solve(int q){
    for (int i=1;i<=n;++i) b[i]=((q-a[i])%mod+mod)%mod;
    memset(f,0,sizeof(f));
    f[0][0]=1;
    for (int i=1;i<=n;++i){
        f[i&1][0]=1;
        for (int j=1;j<=i;++j)
            f[i&1][j]=f[i-1&1][j],
            f[i&1][j]+=f[i-1&1][j-1]*b[i]%mod,f[i&1][j]%=mod;
    }
    return f[n&1][k];
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>k;
    for (int i=1;i<=n;++i) cin>>a[i];
    int Q;cin>>Q;
    while (Q--){
        int opt;cin>>opt;
        if (opt==1){
            int q,i,d;cin>>q>>i>>d;
            int la=a[i];a[i]=d;
            cout<<solve(q)<<'\n';a[i]=la;
        }else{
            int q,l,r,d;cin>>q>>l>>r>>d;
            for (int i=l;i<=r;++i) a[i]+=d;
            cout<<solve(q)<<'\n';
            for (int i=l;i<=r;++i) a[i]-=d;
        }
    }
    return 0;
}