1420D - Rescue Nibel! (组合数+排序)

落日映苍穹つ 2021-07-17 01:36 193阅读 0赞

[题目][Link 1]

思路：首先给所有的区间排个序，使L（左边界）小的排在前面,然后开始枚举，每枚举完一个区间把该区间的R(右边界)加入到multiset中，如果遇到当前区间的L大于multiset中的R值则抛出该R,因为L是递增的该R也不会对之后的区间产生贡献，对于每个枚举的区间ans+=cal(multiset.size(),k-1)表示已经选定了该区间再从multiset之前出现过的区间中选出k-1个区间（不符合条件的R>该L的已经被erase了），这种方法是不重不漏的。

现在解释一下，为何这是不重不漏的。首先每一个区间的贡献产生于两个阶段，第一个是它刚遍历到时会加上一个和已经遍历过的区间选出k-1个的组合数，这时它和已经遍历过的所有区间能组成集合的情况加上了。第二，我们将该区间的R加到了multiset中，每当我们遍历一个后面的区间它都会和这个区间的R比较看能不能与那个后面的区间相交产生贡献，所以在这该区间与所有后面的区间产生的贡献也会计算到。由此遍历完所有空间后对于每一个空间产生的贡献都会加到，它是不漏的。再看它为何是不重的，容易看出我们刚开始遍历到时选出k-1已遍历的组合情况是不重的，而对于之后有没有可能会与前面遍历到的冲突呢？其实是不会的因为后面一定会选择一个新的区间，而这个区间是之前没遍历过的，所以后面的每一种情况也不会和前面重合。由此可见按此种方法是不重不漏的，可能说的啰嗦了一些，不知道大家能不能理解。

#include<iostream>
    #include<set>
    #include<algorithm>
    #define pii pair<int,int>
    #define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
    using namespace std;
    typedef long long ll;
    const int Max = 1e6 + 5;
    pii lst[Max];
    int Mod = 998244353;
    
    ll f[Max];
    ll qpow(ll a, ll b) { 
        ll ans = 1, base = a;
        while (b) { 
            if (b & 1) ans = ans * base % Mod;
            base = base * base % Mod;
            b >>= 1;
        }
        return ans;
    }
    void init() { 
        f[0] = 1;
        for (int i = 1;i <= 1e6;i++) { 
            f[i] = f[i - 1] * i % Mod;
        }
    }
    ll cal(ll n, ll m) { 
        if (n < m) return 0;
        return 1ll * f[n] * qpow(f[m], Mod - 2) % Mod * qpow(f[n - m], Mod - 2) % Mod;
    }
    
    int main()
    { 
        int n, k;cin >> n >> k;
        for (int i = 1;i <= n;i++)cin >> lst[i].first >> lst[i].second;
        sort(lst + 1, lst + 1 + n);
        multiset<int> set;
        ll ans = 0;init();
        for (int i = 1;i <= n;i++)
        { 
            while (!set.empty() && *set.begin() < lst[i].first) {  set.erase(set.begin()); }
            ans = (ans + cal(set.size(), k - 1)) % Mod;
            set.insert(lst[i].second);
        }
        cout << ans;
    }

[Link 1]: https://codeforces.com/problemset/problem/1420/D