AtCoder Beginner Contest 205

补题链接：Here

ABC 水题跳过

D - Kth Excluded

给定 N 个正整数序列： A = ( ) 和 Q 查询。
在第 i 个查询 ( ) 中，给定一个正整数 K ，在与 不同的正整数中找出第 K 个最小的整数。

二分找第一个比K值大的下标然后累加即可

ll a[N];
void solve() {
    int n, q;
    cin >> n >> q;
    for (int i = 0; i < n; ++i) {
        cin >> a[i], a[i] -= i;
    }
    ll k;
    while (q--) {
        cin >> k;
        cout << upper_bound(a, a + n, k) - a + k << "\n";
    }
}

E - White and Black Balls

【题意待补】

一道经典组合数利用的构造题

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1e9 + 7;
int n, m, k;
int qp(int x, int y) {
    if (x == 0) return 0;
    if (x == 1) return 1;
    if (y == 0) return 1;
    if (y == 1) return x;
    int ans = qp(x, y / 2);
    (ans *= ans) %= mod;
    if (y & 1) (ans *= x) %= mod;
    return ans;
}
int C(int x, int y) {
    if (y < 0) return 0;
    int res = 1, an = 1;
    for (int i = x; i >= x - y + 1; i--)
        (res *= i) %= mod;
    for (int i = 1; i <= y; i++)
        (an *= i) %= mod;
    return (qp(an, mod - 2) * res) % mod;
}
signed main() {
    cin >> n >> m >> k;
    if (n - m > k) {
        puts("0");
        return 0;
    }
    cout << (C(n + m, n) - C(n + m, n - k - 1) + mod) % mod;
    return 0;
}