牛课暑假多校第九场H prefix sum

傷城~ 2022-05-16 10:11 102阅读 0赞

[传送门][Link 1]

![70][]

假如a\[0\]\[1\]=1，那他对后面的影响如图所示，斜着看可以发现，是杨辉三角，假如k=3，x=3，a\[0\]\[1\]对他的影响是C(4， 2)，a\[0\]\[2\]对他的影响是C(3,2)，a\[0\]\[3\]对他的影响是C（2,2）；所以a\[0\]\[i\]对他的影响是C(k+x-1-i,k-1),![a\[k\]\[x\]=\\sum\_\{i=1\}^\{x\}\\binom\{x+k-1-i\}\{k-1\}\*a\[0\]\[i\]][a_k_x_sum_i_1_x_binom_x_k-1-i_k-1_a_0_i],我们将式子转化为![\\sum\_\{j=1\}^\{k-1\} \\binom\{x\}\{j\}\\sum\_\{i=1\}^\{x\}\\binom\{k-1-i\}\{k-1-j\}\*a\[0\]\[x\]][sum_j_1_k-1_ _binom_x_j_sum_i_1_x_binom_k-1-i_k-1-j_a_0_x],这样对于后面的\\sum可以通过树状数组维护前缀和。对于负数的组合数，![37d3d539b6003af3f7166cdf3f2ac65c1138b6e5.jpg][]，对于组合数递推公式仍然满足。

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N=2e5+10;
    const int mo=1e9+7;
    int n, m, k, x;
    ll y, s[50][N];
    
    ll inv[N];
    
    void init(){
        inv[1]=1;
        for(int i=2; i<N; i++)
            inv[i]=inv[mo%i]*(mo-mo/i)%mo;
    }
    
    void upd(int id, int x, ll v){
        for(;x<N;x+=x&-x){
            s[id][x]=(s[id][x]+v+mo)%mo;
        }
    }
    ll sum(int id, int x){
        ll ret=0;
        for(; x>0; x-=x&-x)
            ret=(ret + s[id][x])%mo;
        return ret;
    }
    
    int main(){
    
        init();
    
        scanf("%d%d%d", &n, &m, &k);
        int o;
        while(m--){
            scanf("%d", &o);
            if(o==0){
                ll u=1;
                scanf("%d%lld", &x, &y);
                for(int i=0; i<k; i++){
                    upd(i, x, u*y%mo);
                    u=u*(k-1-x-i)%mo*inv[i+1]%mo;
                }
            }
            else{
                scanf("%d", &x);
                ll ans=0, u=1;
                for(int i=0; i<k; i++){
                    ans=(ans+u*sum(k-1-i, x)%mo)%mo;
                    u=u*(x-i)%mo*inv[i+1]%mo;
                    if(u<0) u+=mo;
    
                }
                //cout<<"******"<<endl;
                printf("%lld\n", ans);
            }
        }
        return 0;
    }

另一种分块的思想也很巧妙，题目给的时间是3秒，总复杂度3e8肯定没问题，1e5次操作，我们如果将更新操作累加到1000次再暴力更新，暴力更新复杂度是O（n\*k），最多1e2次更新，总的时间复杂度是1e5\*1e2\*40=1e8左右，如果是询问，因为1000次以内不更新，如果有询问，就看哪个更新对询问的位置产生影响，这样的话复杂度是1000，最多1e5的复杂度，所以分块时间会优化特别多。

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N=2e5+10;
    const int mo=1e9+7;
    int n, m, k, x, block;
    ll y, s[N], a[N], dp[2][N];
    struct Qu{
        ll v, x;
    }Q[N];
    
    ll inv[N], finv[N], fac[N];
    void init(){
        inv[1]=finv[0]=finv[1]=fac[0]=fac[1]=1;
        for(int i=2; i<N; i++){
            inv[i]=inv[mo%i]*(mo-mo/i)%mo;
            fac[i]=1ll*i*fac[i-1]%mo;
        }
        for(int i=2; i<N; i++)
            finv[i]=finv[i-1]*inv[i]%mo;
    }
    
    ll C(ll n, ll m){
        if(n<m) return 0;
        return fac[n]*finv[m]%mo*finv[n-m]%mo;
    }
    
    ll query(int x){
        ll sum=s[x];
        for(int i=1; i<=block; i++){
            //cout<<Q[i].v<<endl;
            if(Q[i].x<=x)
                sum=(sum+C(x-Q[i].x+k-1, k-1)*Q[i].v)%mo;
        }
        return sum;
    }
    
    void upd(){
        block=0;
        int f=0;
        for(int i=1; i<=n; i++) dp[0][i]=a[i];
        for(int i=1; i<=k; i++){
            f^=1;
            dp[f][1]=dp[f^1][1];
            for(int j=2; j<=n; j++){
                dp[f][j]=(dp[f][j-1]+dp[f^1][j])%mo;
            }
        }
        for(int i=1; i<=n; i++) s[i]=dp[f][i];
    
    }
    
    int main(){
    
        init();
    
        scanf("%d%d%d", &n, &m, &k);
        int o;
        while(m--){
            scanf("%d", &o);
            if(o==0){
                ++block;
                scanf("%lld%lld", &Q[block].x, &Q[block].v);
                //cout<<Q[block].x<<" "<<Q[block].v<<endl;
                a[Q[block].x]+=Q[block].v;
                a[Q[block].x]%=mo;
                if(block>=2000)
                    upd();
            }
            else{
                scanf("%d", &x);
                //printf("%lld\n", s[x]);
                printf("%lld\n", query(x));
            }
        }
        return 0;
    }

[Link 1]: https://www.nowcoder.com/acm/contest/147/H
[70]: /images/20220516/86e9e42b9a864356b123a5c89a07ae26.png
[a_k_x_sum_i_1_x_binom_x_k-1-i_k-1_a_0_i]: https://private.codecogs.com/gif.latex?a%5Bk%5D%5Bx%5D%3D%5Csum_%7Bi%3D1%7D%5E%7Bx%7D%5Cbinom%7Bx&plus;k-1-i%7D%7Bk-1%7D*a%5B0%5D%5Bi%5D
[sum_j_1_k-1_ _binom_x_j_sum_i_1_x_binom_k-1-i_k-1-j_a_0_x]: https://private.codecogs.com/gif.latex?%5Csum_%7Bj%3D1%7D%5E%7Bk-1%7D%20%5Cbinom%7Bx%7D%7Bj%7D%5Csum_%7Bi%3D1%7D%5E%7Bx%7D%5Cbinom%7Bk-1-i%7D%7Bk-1-j%7D*a%5B0%5D%5Bx%5D
[37d3d539b6003af3f7166cdf3f2ac65c1138b6e5.jpg]: https://gss1.bdstatic.com/-vo3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D294/sign=5c1e256302fa513d55aa6bd7096c554c/37d3d539b6003af3f7166cdf3f2ac65c1138b6e5.jpg