CF1717D 题解

· · 题解

0. 前言
重在思路，不在代码。
前置知识：逆元

1. 分析
赞助商修改的 k 次比赛结果可以是任意的，但是问的是最坏情况，也就是尽可能让编号大的获胜。如果想让一个人获胜，只需要把他所有的比赛全都调成赢即可。

注意，打败他的人在打败他之后进行的场次赢的计入他的胜利中，就比如下图：6 号位被 5 号位打败，然后 5 号位打败 7 号位，接着 1 号位打败 5 号位，那么就是 6 号位算是赢了一场（5 打败 1）。因为如果让 6 打败 5 的话，因为预先设定的是 5 6 之间的胜者打败了 7 8 之间的胜者，所以如果能打败一个人就能抢走他这场比赛后应有的全部的胜利场次。

如果他输了 x<k 场，那么赞助商就可以让他胜出。

蓝色=赢，黑色=输，数字仅表示位置不表示编号

如果赞助商想让 1 号位的人赢，就需要 k\ge 0。而 2,3,5 号位需要 k\ge 1。
如果 k=1，那么有四个人永远都不会最终胜出，就可以把编号最大的 5 6 7 8 排入其中，所以最终结果是 4。而可能胜出的人分别赢了 0,1,\dots,k 场，相当于在每个人的 n 场里面选择不超过 k 场作为赢的，总的方案数就是答案。如果恰好选择 i 场，那么这部分的结果将是 C_n^i。
而根据公式，C_n^i=C_n^{i+1}\times(i+1)\div(n-i)，可以通过预处理逆元 O(n) 预处理组合数。最终时间复杂度 O(n)。

#include<iostream>
#include<cstdio>
#define maxn 100005
#define mod 1000000007

using namespace std;

long long n, k, inv[maxn], C[maxn], ans;

long long qpow(int p, int q) {
    if(q == 0) return 1ll;
    if(q == 1) return p;
    long long kkk = qpow(p, q >> 1);
    return kkk * kkk % mod * ((q & 1) ? p : 1ll) % mod;
} //就是用来计算2的幂的，也可以用每次左移1取模的方式

int main() {
    scanf("%lld %lld", &n, &k);
    inv[1] = 1;
    for(int i = 2; i <= n; i++) {
        inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    }
    C[n] = 1;
    for(int i = n - 1; i >= 0; i--) {
        C[i] = C[i + 1] * (i + 1) % mod * inv[n - i] % mod;//预处理组合数
    }
    for(int i = n; i > k; i--) {//这里是因为之前有过多次组合数带取模正向枚举结果k>n的然后炸飞的经历，已经养成这样的习惯了
        ans += C[i];
        ans %= mod;
    }
    cout << (qpow(2, n) - ans + mod) % mod << endl;//减完之后可能是负的，所以要加一个mod再取模
}