1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<algorithm>
 5 using namespace std;
 6 #define LL long long 
 7 struct fhsb{
 8     LL x,y;
 9 };
10 const LL N=1e6+5,P=2147483648;
11 LL x[N],y[N],C[N][20];
12 LL t[N],s[N],w;;
13 LL lie[N],hang[N];
14 fhsb p[N];
15 bool cmp(fhsb a,fhsb b){if(a.x==b.x)return a.y<b.y;else return a.x<b.x;}
16 inline LL lowbit(LL x){return x&(-x);}
17 inline LL read()
18 {
19     LL x=0,f=1;char c=getchar();
20     while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();}
21     while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();}
22     return x*f;
23 }
24 inline void update(LL x,LL v)
25 {
26     v%=P;
27     while(x<=w)
28     {
29         s[x]=(s[x]+v)%P;
30         x+=lowbit(x);
31     }
32 }
33 
34 inline LL sum(LL x)
35 {
36     int res=0;
37     while(x)
38     {
39         res=(res+s[x])%P;
40         x-=lowbit(x);
41     }
42     return res;
43 }
44 int main()
45 {
46     freopen("cnm.txt","r",stdin);
47     read();read();
48     w=read();
49     for(LL i=1;i<=w;++i) 
50     {
51         x[i]=p[i].x=read();
52         y[i]=p[i].y=read();
53     }
54     LL k=read();
55     C[0][0]=1;
56     for(LL i=1;i<=w;++i)
57     {
58         C[i][0]=1;
59         for(LL j=1;j<=k;++j)
60             C[i][j]=(C[i-1][j]+C[i-1][j-1])%P;
61     }
62     sort(x+1,x+w+1);
63     sort(y+1,y+w+1);
64     for(LL i=1;i<=w;++i) 
65         p[i].x=lower_bound(x+1,x+w+1,p[i].x)-x,lie[p[i].x]++;
66     for(LL i=1;i<=w;++i) 
67         p[i].y=lower_bound(y+1,y+w+1,p[i].y)-y,hang[p[i].y]++;
68     sort(p+1,p+w+1,cmp);
69     LL down=1,ans=0;
70     for(LL i=1;i<w;++i)
71     {
72         if(p[i].x==p[i-1].x) down++;
73         else down=1;
74         LL up=lie[p[i].x]-down;
75         if(up)
76         {
77             LL ccf=p[i+1].y-1;
78             ans+=C[down][k]*C[up][k]%P*((sum(ccf)-sum(p[i].y)%P+P)%P);
79         }
80         ++t[p[i].y];
81         LL now=C[t[p[i].y]][k]*C[hang[p[i].y]%P-t[p[i].y]][k]%P;
82         LL pre=(sum(p[i].y)-sum(p[i].y-1)+P)%P;
83         update(p[i].y,((now-pre+P)%P));
84     }
85     printf("%lld\n",((ans+P)%P+P)%P);
86     return 0;
87 }

 1 #include<map>//n2 bruce
 2 #include<cstdio>
 3 #include<algorithm>
 4 #define unt unsigned int
 5 #define maxn 100005
 6 #define mod 0x7fffffff
 7 using namespace std;
 8 int n,m;
 9 int c[maxn][11];
10 struct tree
11 {
12     int x,y;
13     bool friend operator <(tree a,tree b)
14     {return a.x==b.x?a.y<b.y:a.x<b.x;}
15 }p[maxn];
16 int szx,szy,z[maxn];
17 int binx[maxn],biny[maxn];
18 int ans;
19 void init()
20 {
21     scanf("%d%d%d",&n,&n,&n);
22     for(int i=1;i<=n;++i)
23         scanf("%d%d",&p[i].x,&p[i].y);
24     scanf("%d",&m);
25     map<int,int>mpx,mpy;
26     z[0]=-1;
27     for(int i=1;i<=n;++i) z[i]=p[i].x;
28     sort(z+1,z+1+n);
29     for(int i=1;i<=n;++i) 
30         if(z[i]!=z[i-1])
31             mpx[z[i]]=++szx;
32     for(int i=1;i<=n;++i) p[i].x=mpx[p[i].x],++binx[p[i].x];
33 
34     for(int i=1;i<=n;++i) z[i]=p[i].y;
35     sort(z+1,z+1+n);
36     for(int i=1;i<=n;++i)
37         if(z[i]!=z[i-1]) 
38             mpy[z[i]]=++szy;
39     for(int i=1;i<=n;++i) p[i].y=mpy[p[i].y],++biny[p[i].y];
40 
41     sort(p+1,p+1+n);
42     for(int i=0;i<=n;++i)
43     {
44         c[i][0]=1;
45         for(int j=1;j<=m&&j<=i;++j)
46             c[i][j]=c[i-1][j-1]+c[i-1][j];
47     }
48 }
49 int bin[maxn],ab,cnt;
50 void calc(int x)
51 {
52     for(int i=1;i<=szy;++i)
53     {
54         if(x==p[cnt+1].x&&i==p[cnt+1].y)
55         {++ab;++bin[i];++cnt;continue;}
56         ans+=c[bin[i]][m]*c[biny[i]-bin[i]][m]*c[ab][m]*c[binx[x]-ab][m];
57         //printf("%d %d (%d %d) up %d lf %d\n",x,i,binx[x],biny[i],ab,bin[i]);
58     }
59 }
60 int main()
61 {
62     init();
63     for(int i=1;i<=szx;++i)
64     {
65         ab=0;
66         calc(i);
67     }
68     printf("%d\n",ans&mod);
69 }
70 /*
71 5 6
72 13
73 0 2
74 0 3
75 1 2
76 1 3
77 2 0
78 2 1
79 2 4
80 2 5
81 2 6
82 3 2
83 3 3
84 4 3
85 5 2
86 2
87 */