Codeforces Round #361 (Div. 2) E. Mike and Geometry Problem

题目大意:给你n个区间，求任意k个区间交所包含点的数目之和。

题目思路:将n个区间都离散化掉，然后对于一个覆盖的区间，如果覆盖数cnt>=k，则数目应该加上区间长度*（cnt与k的组合数） ans=ans+(len*C(cnt,k))%mod;

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <algorithm>

#include <cstring>

#include <stack>

#include <cctype>

#include <queue>

#include <string>

#include <vector>

#include <set>

#include <map>

#include <climits>

#define lson root<<1,l,mid

#define rson root<<1|1,mid+1,r

#define fi first

#define se second

#define ping(x,y) ((x-y)*(x-y))

#define mst(x,y) memset(x,y,sizeof(x))

#define mcp(x,y) memcpy(x,y,sizeof(y))

using namespace std;

#define gamma 0.5772156649015328606065120

#define MOD 1000000007

#define inf 0x3f3f3f3f

#define N 200005

#define maxn 1050

typedef pair<int,int> PII;

typedef long long LL;

int n,k,m,cnt;

LL fac[N];

struct Node{

    int x,v;

    bool operator<(const Node&a)const{

        if(x==a.x)return v>a.v;

        return x<a.x;

    }

}node[N<<];

int a[N<<],sum[N<<];

int has[N<<];

LL ksm(LL a,LL b){

    LL res=;

    while(b){

        if(b&)res=res*a%MOD;

        b>>=;

        a=a*a%MOD;

    }

    return res;

}

LL C(LL n,LL m){

    if(n<m||m<)return ;

    LL s1=fac[n],s2=fac[n-m]*fac[m]%MOD;

    return s1*ksm(s2,MOD-)%MOD;

}

int main(){

    int i,j,group,x,y,v;

    fac[]=;cnt=;

    for(i=;i<N;++i)fac[i]=fac[i-]*i%MOD;

    scanf("%d%d",&n,&k);

    for(i=;i<=n;++i){

        scanf("%d%d",&x,&y);

        node[cnt].x=x;node[cnt++].v=;

        node[cnt].x=y+;node[cnt++].v=-;

    }

    sort(node,node+cnt);

    LL ans=,la,num=; ///la是区间左端点

    for(i=;i<cnt;++i){

        if(num>=k) ans=(ans+(node[i].x-la*1ll)*C(num,k))%MOD;

        la=node[i].x;

        num+=node[i].v;

    }

    printf("%I64d\n",ans);

    return ;

}

秒客网

Codeforces Round #361 (Div. 2) E. Mike and Geometry Problem

相关文章