当前位置: 代码迷 >> 综合 >> Codeforces Round #672 (Div. 2) D. Rescue Nibel! (组合数,方案数,优先队列)
  详细解决方案

Codeforces Round #672 (Div. 2) D. Rescue Nibel! (组合数,方案数,优先队列)

热度:0   发布时间:2024-02-24 12:51:34.0

从一堆区间里选k个有公共区间的(l,r),有几种选法
(1) 按照左端点排序 //线段集合常用操作
(2) 枚举每个线段,看当前线段作为k个线段中最右侧的那个的话能有几种方案数,即对于每个线段,枚举他之前的线段中,右端点>=该线段左端点的有多少,如果大于k-1个就组合数,这里统计前面线段的个数用STL随便搞了搞

#define int ll 
const int MOD = 998244353;
ll fac[MX];
void init()
{
    fac[0] = 1;for (ll i = 1; i < MX; i++)fac[i] = fac[i - 1] * i % MOD;
}
ll exgcd(ll a, ll b, ll &x, ll &y)
{
    if (!b){
    x = 1;y = 0;return a;}ll d = exgcd(b, a % b, y, x);y -= a / b * x;return d;
}ll inv(ll a, ll n)
{
    ll x, y;exgcd(a, n, x, y);return (x + n) % n;
}ll C(ll n, ll m)
{
    return fac[n] * inv(fac[m] * fac[n - m] % MOD, MOD) % MOD;
}void solve()
{
    int n,k;cin>>n>>k;priority_queue<int,vector<int>, greater<int>>q;vector<pair<int,int> >v(n);rep(i,n) cin>>v[i].first>>v[i].second;sort(all(v));ll ans=0;for(auto x:v){
    while(q.size()&&q.top()<x.first) q.pop();if(q.size()>=k-1) ans=(ans+C(q.size(),k-1))%MOD;q.push(x.second);}cout<<ans<<endl;
}
  相关解决方案