P6533 [COCI2015-2016#1] RELATIVNOST

題目大意

小$L$在賣畫。這些畫分為彩色畫和黑白畫，小$L$希望有至少$c$個人會買走他至少一張彩色畫。

第$i$個人至多會購買$a_i$張彩色畫或者$b_i$張黑白畫，且每個人至少購買一張畫。

每個人只能選擇購買彩色畫或黑白畫。

有$q$次修改，每次修改會選擇一個$i$并修改$a_i$和$b_i$。求每次修改之后能滿足小$L$的要求的買畫的方案數。輸出答案模$10^4+7$后的值。

$1\le n,q\le 10^5,1\le c\le 20$

時間限制$4000ms$，空間限制$32MB$。

題解

設$f_{i,j}$表示前$i$個人有$j$個人選擇彩色畫的方案數，則轉移式為

$$f_{i,j}=f_{i?1,j?1}\times a_i+f_{i?1,j}\times b_i$$

因為有修改，所以我們考慮用線段樹來優化。用線段樹維護每一個區間的方案數，那么

$$tr[k].f[i+j]+=tr[lc].f[i]\times tr[rc].f[j]$$

在只有一個人時，$tr[k].f[1]=a_i,tr[k].f[0]=b_i$。

空間限制為$32MB$，對于$\text{int}$類型能開$24\times 1024\times 1024/4=8388608$的大小。線段樹的大小為$4nc=8000000$，$a,b$數組的大小都是$10^5$，是可行的。注意空間復雜度，能節省的空間盡量節省。

時間復雜度為$O(n{c}^2\log n)$，空間復雜度為$O(nc)$。

code

#include<bits/stdc++.h>
#define lc k<<1
#define rc k<<1|1
using namespace std;
const int N=100000;
const int mod=1e4+7;
int n,c,q,a[N+5],b[N+5],tr[4*N+5][21];
void pt(int k){for(int i=0;i<=c;i++) tr[k][i]=0;for(int i=0;i<=c;i++){for(int j=0;j<=c;j++){tr[k][min(i+j,c)]=(tr[k][min(i+j,c)]+tr[lc][i]*tr[rc][j])%mod;}}
}
void build(int k,int l,int r){if(l==r){tr[k][1]=a[l]%mod;tr[k][0]=b[l]%mod;return;}int mid=l+r>>1;build(lc,l,mid);build(rc,mid+1,r);pt(k);
}
void ch(int k,int l,int r,int p,int x,int y){if(l==r&&l==p){tr[k][1]=x%mod;tr[k][0]=y%mod;return;}int mid=l+r>>1;if(p<=mid) ch(lc,l,mid,p,x,y);else ch(rc,mid+1,r,p,x,y);pt(k);
}
int main()
{scanf("%d%d",&n,&c);for(int i=1;i<=n;i++) scanf("%d",&a[i]);for(int i=1;i<=n;i++) scanf("%d",&b[i]);build(1,1,n);scanf("%d",&q);while(q--){int p,x,y;scanf("%d%d%d",&p,&x,&y);ch(1,1,n,p,x,y);printf("%d\n",tr[1][c]);}return 0;
}