@OceanEye8年前
05/11
16:46
这题很裸，离散化一维本来想写个动态开点的线段树的之后逐行处理答案。
大概就是经过一个点就更改对应节点上的value，这个值要用组合数来算一下。
懒得看怎么处理附属就只去看了HZWER的题解……后来自己写了个很暴力的东西:-D。
具体怎么做下面也有:-D大力安利HZWER
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 |
/************************************************************** Problem: 1227 User: OceanEYe Language: C++ Result: Accepted Time:2304 ms Memory:3636 kb ****************************************************************/ #include <cstdio> #include <algorithm> #include <cstring> #include <cstdlib> #include <iostream> #define ll long long #define INF 1000000000 #define p(x) ('0'<=x&&x<='9') #define P 2147483648LL char cc; int C; template <class T> void read( T &x ){ x=0; cc=getchar(); C=1; while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); } while(p(cc)) { x=x*10+cc-48; cc=getchar(); } x*=C; } using namespace std; #define N 100010 #define lb(x) (x&-x) int Arr[N]; inline void add(int pos,int val){ while(pos<=N) { Arr[pos]+=val; pos+=lb(pos); } } inline int query(int pos){ unsigned int ret=0; while(pos) { ret+=Arr[pos]; pos-=lb(pos); } return ret; } #undef lb struct pt { int x,y; }pool[N]; bool comp(const pt &x,const pt &y){ return x.x==y.x?x.y<y.y:x.x<y.x; } int bin[N],cnt[N],_[N],n,a,b,k; int calc(int x,int k){ if(x<k) return 0; ll ret=1; for(int i=1;i<=k;i++) ret=(ll)ret*(x-i+1)/i; return ret%P; } int ans; void solve(){ int tmp,node2,__; for(int node=1;node<=n;){ tmp=1; node2=node; __=0; while(pool[node2].x==pool[node2+1].x) node2++,tmp++; for(;node<node2;node++){ __++; ans+=(ll)(query(pool[node+1].y-1)-query(pool[node].y))*calc(__,k)*calc(tmp-__,k)%P; add(pool[node].y,(ll)-calc(_[pool[node].y],k)*calc(cnt[pool[node].y]-_[pool[node].y],k)%P); _[pool[node].y]++; add(pool[node].y,(ll)calc(_[pool[node].y],k)*calc(cnt[pool[node].y]-_[pool[node].y],k)%P); } add(pool[node].y,(ll)-calc(_[pool[node].y],k)*calc(cnt[pool[node].y]-_[pool[node].y],k)%P); _[pool[node].y]++; add(pool[node].y,(ll)calc(_[pool[node].y],k)*calc(cnt[pool[node].y]-_[pool[node].y],k)%P); node=node2+1; } } void pre(){ read(a); read(b); read(n); for(int i=1;i<=n;i++) { read(pool[i].x); read(pool[i].y); bin[i]=pool[i].y; } sort(bin+1,bin+1+n); for(int i=1;i<=n;i++) { pool[i].y=lower_bound(bin+1,bin+1+n,pool[i].y)-bin; cnt[pool[i].y]++; } sort(pool+1,pool+1+n,comp); read(k); } int main(){ pre(); solve(); if(ans<0) ans+=P; printf("%d",ans); return 0; } |