多校⑨ 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(); }