竞赛讨论区 > 多校⑨ Prefix Sum 分块暴力
头像
CToshi
发布于 2018-08-17 20:49
+ 关注

多校⑨ Prefix Sum 分块暴力

题意略
思路:先来一种暴力的,每次修改后O(n*k)维护整个矩阵,查询O(1),考虑对操作分块,当查询数达到blocksize时,才维护整个矩阵,否则不更新,此时需要考虑的问题是:没有维护到矩阵的修改对查询有什么影响?
问题转化:设矩阵为v,矩阵的值的计算方式是v[i][j] = v[i-1][j] + v[i][j-1],每一个格的值都是左边的值加上上面的值,换一个方式,我们让v[i+1][j] += v[i][j],v[i][j+1] += v[i][j],让一个格子的值自己加到右边和下边的格子上,则对于第一行的格子v[0][i],它对第k行的格子v[k][j]都有一个贡献,贡献是该数的值v[0][i]乘上一个常数A,A等于,从v[0][i]格子出发,只能往右或往下走,走到v[k][j]格子的方案数,用插板法,得到A = C(k + j - i - 1, j - i) (其中j >= i) 
块大小的确定:考虑时间3秒,运算次数3e8,维护整个矩阵的时间是O(n*k) = 4e6,可做3e8/4e6 = 75次维护,则取块大小为100000/75 = 1333(但其实大佬取2791跑得更快)
代码
#include<bits/stdc++.h>
#define pii pair<int,int>
#define X first
#define Y second
#define PB push_back
#define MP make_pair
#define mset(var,val) memset(var,val,sizeof(var))
#define scd(a) scanf("%d",&a)
#define scdd(a,b) scanf("%d%d",&a,&b)
#define scddd(a,b,c) scanf("%d%d%d",&a,&b,&c)
using namespace std;

typedef long long ll;
const int N = 1e6+10;
ll f[N];
ll invf[N];
const int mod = 1000000007;
ll qpow(ll a,ll b){
    ll ret=1;
    while(b){
        if(b&1)ret=ret*a%mod;
         b>>=1;
         a=a*a%mod;
    }
    return ret;
}
ll inv(ll a){
    return qpow(a, mod-2);
}
void init(){
    f[0]=1;for(int i = 1;i<N;i++)f[i]=f[i-1]*i%mod;
    invf[N-1] = inv(f[N-1]);
    for(int i = N-2;i>=0;i--)invf[i]=invf[i+1]*(i+1)%mod;//预处理阶乘逆元
}
ll C(int n,int m){return f[n]*invf[n-m]%mod*invf[m]%mod;}
pii p[N];
ll v[44][N];
int n,k;
void update(){
    for(int i = 1;i<=k;i++){
        for(int j = 1;i<=n;i++){
            v[i][j] = (v[i-1][j] + v[i][j-1])%mod;
        }
    }
}
void work(){
    int m;scddd(n,m,k);
    for(int i = 0;i<m;i++){
        int d;scd(d);
        if(!d){
            int x,y;scdd(x,y);
            p[i].X = x;p[i].Y = y;
        }else{
            int x;scd(x);
            p[i].X = x;
            p[i].Y = -1;
        }
    }
    int sz = 1333;
    vector<pii> ve;
    for(int i = 0;i<m;i++){
        if(p[i].Y < 0){
            int pos = p[i].X;
            ll ans = v[k][pos];
            for(int j = 0;j<ve.size();j++){
                pii now = ve[j];
                if(now.X > pos)continue;
                ans = (ans + C(k+pos-now.X-1, pos-now.X)*now.Y)%mod;
            }
            printf("%lld\n", ans);
        }else{
            ve.PB(p[i]);
            if(ve.size() == sz){
                for(int j = 0;j<sz;j++){
                    pii now = ve[j];
                    v[0][now.X] =  (v[0][now.X] + now.Y)%mod;
                }
                update();
                ve.clear();
            }
        }
    }
}
int main() {
    init();
    work();
}

全部评论

(0) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐