牛客网暑期ACM多校训练营（第十场）D Rikka with Prefix Sum （数学）

Rikka with Prefix Sum

题意：

给出一个数组a，一开始全为0，现在有三种操作：

1. 1 L R W，让区间[L,R]里面的数全都加上W；

2. 2 将a数组变为其前缀和数组；

3. 3 L R 询问此时a数组区间[L,R]的和。

题解：

第一种操作我们可以简化为a[L]+W，a[R+1]-W，利用差分数组的思想。

接下来这一步使关键，考虑i这个位置有值a[i]，然后经过多次2操作对后面的值的贡献，先可以从a[i]=1考虑，然后推广就是了= =

发现1这个数对后面位置的贡献随着位置的增加与组合数有关，这个可以自己去找下规律。

然后还有一个就是求区间和的时候，可以从组合数的性质C(i,j)=C(i-1,j-1)+C(i-1,j)去推导。

最后一点，由于一开始我们对区间修改是对点修改的，假设对点修改后进行了i次2操作，现在求区间和时，其实是求i+1次2操作后的区间和，这一步如果之前第二步推好了是很好解决的。

注意上面几点是息息相关的，需要自己耐心地找规律。

另外再稍微提醒一下，由于组合数二维数组预处理空间开不下，所以只能利用阶乘来算，后面取模时就涉及到了逆元。如果不清楚逆元可以去看看费马小定理。

逆元可以直接用快速幂来求，但我直接求T了，所以用一个数组事先预处理一下...

因此要预处理两个数组出来，同时数组长度要开大一倍，这把上面推好了自然就知道了~

给出代码吧：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2e5+,MOD = ;

int t,n,m,tot;

int l[N],r[N],w[N],s[N];

ll fac[N],inv[N];

ll qp(ll a,ll b){

    ll ans = ;

    while(b){

        if(b&) ans=ans*a%MOD;

        a=a*a%MOD;

        b>>=;

    }

    return ans ;

}

ll C(ll a,ll b){

    return fac[a]*qp(fac[b]*fac[a-b]%MOD,MOD-)%MOD;

}

ll query(ll L,ll R,ll cnt){

    if(L-<) return C(cnt+R+,R)%MOD;

    return ((C(cnt+R+,R)-C(cnt+L+,L-))%MOD+MOD)%MOD;

}

int main(){

    scanf("%d",&t);

    fac[]=;

    for(int i=;i<=2e5;i++) fac[i]=fac[i-]*i%MOD;

    while(t--){

        tot=;memset(s,,sizeof(s));

        scanf("%d%d",&n,&m);

        for(int i=;i<=m;i++){

            int op;

            scanf("%d",&op);

            if(op==){

                scanf("%d%d%d",&l[tot],&r[tot],&w[tot]);

                r[tot]++;

                tot++;

            }else if(op==) s[tot-]++;

            else{

                int L,R;

                scanf("%d%d",&L,&R);

                ll ans = ;

                int cnt = ;

                for(int i=tot-;i>=;i--){

                    cnt+=s[i];

                    if(l[i]<=R)

                        ans=(ans+(ll)w[i]*query(max(l[i],L)-l[i],R-l[i],cnt-)%MOD)%MOD;

                    if(r[i]<=R)

                        ans=(ans-(ll)w[i]*query(max(r[i],L)-r[i],R-r[i],cnt-)%MOD+MOD)%MOD;

                }

                printf("%lld\n",ans);

            }

        }

    }

    return ;

}

巴特西

牛客网暑期ACM多校训练营（第十场）D Rikka with Prefix Sum （数学）

最新文章

热门文章