题目

1.cdq分治

每次分成左右两块，用左边那块更新右边的

#include<bits/stdc++.h> using namespace std; const int M=1e9+7; int f[1002][1002],sum[1002][1002],cnt[1000002],i,j,n,m,k,a[1002][1002]; inline char gc(){ static char buf[100000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; } inline int rd(){ int x=0,fl=1;char ch=gc(); for (;ch<48||ch>57;ch=gc())if(ch=='-')fl=-1; for (;48<=ch&&ch<=57;ch=gc())x=(x<<3)+(x<<1)+(ch^48); return x*fl; } void cdq(int l,int r){ if (l==r) return; int mid=l+r>>1; cdq(l,mid); for (int i=1;i<=n;i++) for (int j=l;j<=r;j++) cnt[a[i][j]]=0; int sum=0; for (int i=2;i<=n;i++){ for (int j=l;j<=mid;j++) (sum+=f[i-1][j])%=M,(cnt[a[i-1][j]]+=f[i-1][j])%=M; for (int j=mid+1;j<=r;j++) (f[i][j]+=(sum-cnt[a[i][j]])%M)%=M; } cdq(mid+1,r); } int main(){ n=rd();m=rd();k=rd(); for (i=1;i<=n;i++) for (j=1;j<=m;j++) a[i][j]=rd(); f[1][1]=1; cdq(1,m); printf("%d",(f[n][m]+M)%M); }

2.线段树

动态开点

#include<bits/stdc++.h> using namespace std; const int M=1e9+7; int f[1002][1002],sum[10000002],son[10000002][2],tot,i,j,n,m,k,a[1002][1002],rt[1000002]; inline char gc(){ static char buf[100000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; } inline int rd(){ int x=0,fl=1;char ch=gc(); for (;ch<48||ch>57;ch=gc())if(ch=='-')fl=-1; for (;48<=ch&&ch<=57;ch=gc())x=(x<<3)+(x<<1)+(ch^48); return x*fl; } inline int add(int x,int y){x+=y;if(x>=M)x-=M;return x;} int query(int t,int x,int y,int l,int r){ if (x>y || l>r || !t) return 0; if (x==l && y==r) return sum[t]; int mid=l+r>>1; if (y<=mid) return query(son[t][0],x,y,l,mid); if (mid<x) return query(son[t][1],x,y,mid+1,r); return (query(son[t][0],x,mid,l,mid)+query(son[t][1],mid+1,y,mid+1,r))%M; } void update(int &t,int x,int l,int r,int v){ if (!t) t=++tot; sum[t]=add(sum[t],v); if (l==r) return; int mid=l+r>>1; if (x<=mid) update(son[t][0],x,l,mid,v); else update(son[t][1],x,mid+1,r,v); } int main(){ n=rd();m=rd();k=rd(); for (i=1;i<=n;i++) for (j=1;j<=m;j++) a[i][j]=rd(); f[1][1]=1; update(rt[0],1,1,m,1); update(rt[a[1][1]],1,1,m,1); for (i=2;i<=n;i++){ for (j=1;j<=m;j++) f[i][j]=add(query(rt[0],1,j-1,1,m)-query(rt[a[i][j]],1,j-1,1,m),M); for (j=1;j<=m;j++) update(rt[0],j,1,m,f[i][j]),update(rt[a[i][j]],j,1,m,f[i][j]); } printf("%d",f[n][m]); }