任意門：http://codeforces.com/contest/689/problem/E

E. Mike and Geometry Problem

time limit per test 3 seconds memory limit per test 256 megabytes input standard input output standard output

Mike wants to prepare for IMO but he doesn't know geometry, so his teacher gave him an interesting geometry problem. Let's define?f([l,?r])?=?r?-?l?+?1?to be the number of integer points in the segment?[l,?r]?with?l?≤?r?(say that?). You are given two integers?nand?k?and?n?closed intervals?[li,?ri]?on?OX?axis and you have to find:

In other words, you should find the sum of the number of integer points in the intersection of any?k?of the segments.

As the answer may be very large, output it modulo?1000000007?(109?+?7).

Mike can't solve this problem so he needs your help. You will help him, won't you?

Input

The first line contains two integers?n?and?k?(1?≤?k?≤?n?≤?200?000)?— the number of segments and the number of segments in intersection groups respectively.

Then?n?lines follow, the?i-th line contains two integers?li,?ri?(?-?109?≤?li?≤?ri?≤?109), describing?i-th segment bounds.

Output

Print one integer number?— the answer to Mike's problem modulo?1000000007?(109?+?7) in the only line.

Examples input Copy 3 2
1 2
1 3
2 3 output Copy 5 input Copy 3 3
1 3
1 3
1 3 output Copy 3 input Copy 3 1
1 2
2 3
3 4 output Copy 6 Note

In the first example:

;

;

.

So the answer is?2?+?1?+?2?=?5.

?

大概題意：

有 N 個區間， 從其中取 K 個區間。所以有 C（N， K）種組合， 求每種組合區間交集長度的總和。

解題思路：

丟開區間的角度，從每個結點的角度來看，其實每個結點的貢獻是 C（cnt， K） cnt 為該結點出現的次數， 所以只要O（N）掃一遍統計每個結點的貢獻就是答案。

思路清晰，但考慮到數據的規模，這里需要注意和需要用到兩個技巧：

一是離散化，這里STL里的 vector 和 pair 結合用，結合區間加法的思想進行離散化。

二是求組合數時 除數太大，考慮到精度問題需要用逆元來計算。

?

AC code：

1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn = 2e5+7; 4 const int mod = 1e9+7; 5 long long fac[maxn]; 6 7 long long qpow(long long a,long long b) //快速冪 8 { 9 long long ans=1;a%=mod; 10 for(long long i=b;i;i>>=1,a=a*a%mod) 11 if(i&1)ans=ans*a%mod; 12 return ans; 13 } 14 15 long long C(long long n,long long m) //計算組合數 16 { 17 if(m>n||m<0)return 0; 18 long long s1=fac[n], s2=fac[n-m]*fac[m]%mod; //除數太大，逆元處理 19 return s1*qpow(s2,mod-2)%mod; 20 } 21 int n,k; 22 int l[maxn],r[maxn]; //左端點， 右端點 23 int main() 24 { 25 fac[0]=1; 26 for(int i=1;i<maxn;i++) //預處理全排列 27 fac[i]=fac[i-1]*i%mod; 28 29 scanf("%d%d",&n,&k); 30 for(int i=1;i<=n;i++){ 31 scanf("%d",&l[i]); 32 scanf("%d",&r[i]); 33 } 34 vector<pair<int,int> >op; 35 for(int i=1;i<=n;i++){ //離散化 36 op.push_back(make_pair(l[i]-1,1)); //區間加法標記 37 op.push_back(make_pair(r[i],-1)); 38 } 39 sort(op.begin(),op.end()); //升序排序 40 long long ans = 0; //初始化 41 int cnt=0; 42 int la=-2e9; 43 for(int i=0;i<op.size();i++){ //計算每點的貢獻 44 ans=(ans+C(cnt,k)*(op[i].first-la))%mod; 45 la=op[i].first; 46 cnt+=op[i].second; //該點的前綴和就是該點的出現次數 47 } 48 cout<<ans<<endl; 49 } View Code

?

轉載于:https://www.cnblogs.com/ymzjj/p/9629418.html

總結

以上是生活随笔為你收集整理的Codeforces Round #361 (Div. 2) E. Mike and Geometry Problem 【逆元求组合数 离散化】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。