codeforces 689E E. Mike and Geometry Problem(组合数学)
题目链接:
3 seconds
256 megabytes
standard input
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 definef([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?
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.
Print one integer number — the answer to Mike's problem modulo 1000000007 (109 + 7) in the only line.
3 2
1 2
1 3
2 3
5
3 3
1 3
1 3
1 3
3
3 1
1 2
2 3
3 4
6 题意: 在n个区间里选k个,得到的f等于区间交的点数;求所有的选择方案的和; 思路: 对于每个点可以发现,当这个点被num个线段覆盖时,这个点就会被选C(num,k)次,ans=∑C(num,k);
但是区间很大,点的数目居多,所以不可能一个点一个点的这样算,可以发现,相邻的点如果被相同数目的线段覆盖,那么这些点就可以合并成一个区间,所以ans=∑len*C(num,k),len表示这个区间点的个数;看这个点被覆盖了多少次可以采用跟树状数组那样的方法,左右端点+-1; AC代码:
//#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include <queue>
#include <cmath>
#include <map>
#include <cstring>
#include <algorithm>
#include <cstdio> using namespace std;
#define For(i,j,n) for(int i=j;i<=n;i++)
#define Riep(n) for(int i=1;i<=n;i++)
#define Riop(n) for(int i=0;i<n;i++)
#define Rjep(n) for(int j=1;j<=n;j++)
#define Rjop(n) for(int j=0;j<n;j++)
#define mst(ss,b) memset(ss,b,sizeof(ss));
typedef long long LL;
template<class T> void read(T&num) {
char CH; bool F=false;
for(CH=getchar();CH<''||CH>'';F= CH=='-',CH=getchar());
for(num=;CH>=''&&CH<='';num=num*+CH-'',CH=getchar());
F && (num=-num);
}
int stk[], tp;
template<class T> inline void print(T p) {
if(!p) { puts(""); return; }
while(p) stk[++ tp] = p%, p/=;
while(tp) putchar(stk[tp--] + '');
putchar('\n');
} const LL mod=1e9+;
const double PI=acos(-1.0);
const LL inf=1e18;
const int N=2e5+;
const int maxn=;
const double eps=1e-; int n,k,l[N],r[N];
LL dp[N]; map<int,int>mp; LL pow_mod(int x,LL y)
{
LL s=,base=(LL)x;
while(y)
{
if(y&)s=s*base%mod;
base=base*base%mod;
y>>=;
}
return s;
} void Init()
{
dp[k]=;
For(i,k+,N)
{
LL x=i,temp=pow_mod(x-k,mod-);
dp[i]=dp[i-]*x%mod*temp%mod;
}
}
vector<int>ve;
int main()
{
read(n);read(k);
Init();
For(i,,n)
{
read(l[i]);
mp[l[i]-]++;
ve.push_back(l[i]-);
read(r[i]);
mp[r[i]]--;
ve.push_back(r[i]);
}
sort(ve.begin(),ve.end());
LL ans=;
int num=,prepo=-1e9-;
int w=ve.size();
for(int i=;i<w;i++)
{
int tempo=ve[i],len=tempo-prepo;
if(num>=k)ans=ans+dp[num]*(LL)len%mod,ans%=mod;
if(prepo!=tempo) prepo=tempo,num+=mp[tempo];
}
cout<<ans<<"\n";
return ;
}
最新文章
- HTML5的实用
- PKU 1003解题
- 以策略为导向的VI设计
- [Android] adb 命令 dumpsys activity , 用来看 task 中的activity。 (uninstall virus)
- sql server 2008 express 使用ip登陆 error:40 错误:2
- Python3基础 assert关键字 成功啥事没有,失败了就报错
- Oracle GoldenGate 11.2 OGG-01168(转)
- 安卓Design包之CoordinatorLayout配合AppBarLayout,ToolBar,TabLaout的使用
- 关于latex的使用随笔
- 【转】npm包管理器那些事
- 陌陌架构分享 – Apple Push Notification Service
- spring集成shiro登陆流程(上)
- Python:黑板课爬虫闯关第二关
- 第一个Web应用
- <;数据结构与算法分析>;读书笔记--运行时间计算
- Building Tool(Maven/Gradle)
- centos7 sqoop 1 搭建笔记
- github基本用法
- redis High Availability---Redis Sentinel翻译
- JAVA 加密算法初探DES&;AES