abc205-526互联

B - Permutation Check 16

检查给定数组是不是一个排列

C - POW 63

判断 \(a^c\) 和 \(b^c\) 谁大（int 范围，\(c\ge 1\)，\(a,b\) 可能是负数）

c = c % 2 ? 1 : 2，然后特判相等的情况，最后直接做pow比较

D - Kth Excluded 713

给定无重复正序数组，多次询问不在数组中的第 \(k\) 小的正整数。\(a_i,k\le 1e18\)

预处理数组 \(c_i\) 表示 \(\le a_i\) 的合法数的数量。如果 \(k>c_n\)，答案就是 \(a_n+(k-c_n)\)；否则二分找第一个 \(\ge k\) 的 \(c_i\)，因为是第一个满足的所以 \(a_{i-1}+1<a_i\)，也就是说 \((a_{i-1},a_i)\) 中至少有一个数，答案就在其中，是 \(a_i-1-(c_i-k)\)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 5;
ll n, q, a[N], c[N];
int main() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        c[i] = a[i] - i;
    }
    
    while (q--) {
        ll k; cin >> k;
        if (k > c[n]) cout << a[n] + k - c[n] << '\n';
        else {
            int i = lower_bound(c, c + n + 1, k) - c; // c[i] >= k
            cout << a[i] - 1 - (c[i] - k) << '\n';
        }
    }
    
    return 0;
}

E - White and Black Balls 2025

\(n\) 个白球和 \(m\) 个黑球排一排，要求对任意前缀，白球数量不超过黑球数量 \(+k\)，问方案数。

跟卡特兰数推导方法一样，在网格上走。答案是 \(C_{n+m}^n - C_{n+m}^{n-k-1}\)

然后疯狂WA！注意特判 \(n>m+k\) 时无解

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 2e6 + 5, mod = 1e9 + 7;
ll fact[N], ifac[N];

ll qmi(ll a, ll b) {
    ll s = 1;
    for (; b; b >>= 1) {
        if (b & 1) s = s * a % mod;
        a = a * a % mod;
    }
    return s;
}
ll comb(ll n, ll k) {
    if (n < k) return 0;
    return fact[n] * ifac[k] % mod * ifac[n - k] % mod;
}

int main() {
    fact[0] = 1;
    for (int i = 1; i < N; i++) fact[i] = fact[i - 1] * i % mod;
    ifac[N - 1] = qmi(fact[N - 1], mod - 2);
    for (int i = N - 1; i; i--) ifac[i - 1] = ifac[i] * i % mod;
    
    ll n, m, k;
    cin >> n >> m >> k;
    if (n > m + k) return cout << 0, 0; //特判
    cout << ((comb(n + m, n) - comb(n + m, n - k - 1)) % mod + mod) % mod;
    
    return 0;
}