Madoka and The Corruption Scheme

Created by LXC on Thu Mar 14 12:54:03 2024

https://codeforces.com/problemset/problem/1717/D

ranting: 1900

tag: combinatorics, constructive algorithms, greedy, math

problem

有$2^n$名参赛者，参赛者编号为$1$至$2^n$。

一共有$n$轮比赛，每一轮，参赛者两两比赛，胜者进入下一轮。因此如图所示，赛程图是一个满二叉树。

现在你可以决定每一个参赛者第一轮的初始排列顺序（对应二叉树叶子节点的顺序），并且你可以决定每一场比赛是左边的人胜出或是右边的人胜出（如图红线为胜出者）。你希望第一名的人编号最小。

但是，有另一个人也能操纵比赛。他可以更改任意$k$场比赛的结果。

输出你能确保得第一名的人的编号的最小值，对$10^9+7$取模。

solution

满二叉树从根开始选分支一直到叶子，总共有多少种方案呢？

我们每面临一个分支选左或选右，那么选n轮后就有$2^n$种方案。

我们尽量将小的放在左分支，如果更改k场比赛。

k=0，我们全部选左分支，只有一种方案。

k=1，我们只有一次选了右分支，其他选左分支，有$\binom{n}{1}$，此时能选到的最小的数是$\binom{n}{1} + 1$。

k=2，我们只有2次选了右分支，其他选左分支，有$\binom{n}{2}$，此时能选到的最小的数是$\binom{n}{2} + \binom{n}{1} + 1$。

k=3，我们只有3次选了右分支，其他选左分支，有$\binom{n}{2}$，此时能选到的最小的数是$\binom{n}{3} +\binom{n}{2} + \binom{n}{1} + 1$。

k显然不能大于n，对于选k次能选到的最小的数是$\sum \limits_{0\le i\le k} \binom{n}{i}$。恰好在k=n时满足二项式定理$2^n = (1+1)^n = \sum \limits_{0\le i\le n} \binom{n}{i}1^k1^{n-k}$

基于费马小定理利用快速幂求出$n!$模1e9+7这个质数的逆元，然后$O(n)$求出$u!$以及逆元（$0\le u \le n$）。利用组合公式$\binom{n}{m} = \frac{n!}{m!(n-m)!}$，可以通过与处理的阶乘与阶层逆元$O(1)$求出组合数。

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
using namespace std;

template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

const ll MOD = 1e9+7;
ll fac[N], inv_fac[N];
ll fpow(ll x, ll p, ll m) {
	ll rt = 1;
	while (p) {
		if (p&1) rt *= x, rt %= m;
		x *= x; x %= m;
		p >>= 1;
	}
	return rt;
}
void pre() {
    fac[0] = 1;
    for (int i=1; i<N; i++) {
        fac[i] = fac[i-1]*i%MOD;
    }
    inv_fac[N-1] = fpow(fac[N-1], MOD-2, MOD);
    for (int i=N-2; i>=0; i--) {
        inv_fac[i] = inv_fac[i+1]*(i+1)%MOD;
    }
}
// O(1)
int comb(int n, int m) {
	return fac[n]*inv_fac[m]%MOD*inv_fac[n-m]%MOD;
}

void sol() {
    pre();
    ll n, m;
    cin >> n >> m;
    m = min(n, m);
    ll c = 0;
    for (int i=0; i<=m; i++) {
        c += comb(n, i);
        c %= MOD;
    }
    cout << c << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}