D. Madoka and The Corruption Scheme

题意： 给出一个用满二叉树表示的2^n人参加的锦标赛,每场比赛的结果已经确定,可以改变其中k场比赛的结果,问最终比赛的胜者的最大值最小是多少.

思路： 如果能让一个选手成为胜者,因为我们最多只能改变k场比赛的结果,所以这个选手叶子结点到满二叉树根节点上失败的边数量不能超过k,所以我们把大的数都放到到根节点失败边比较多的结点就可以保证这些选手永远不可能成为胜者,所以问题等价于计算有多少个结点到根节点的路径中失败边的数量大于k,用组合数C(n,k+1)+C(n,k+2)+...+C(n,n)计算一下即可，然后答案就是2^n-x.由二项式定理知：2^n-x=C(n,0)+C(n,1)+...+C(n,k).

同时也可以正向思考，所有可能成为胜者的节点到根节点路径上失败边的数目必须小于等于k，这样进行k次操作后才可能让失败边数量为0，即成为胜者，所以答案x=C(n,0)+C(n,1)+...+C(n,min(n,k)).

本题的关键是将能否胜利与到根节点路径中的失败边的数目关联起来。

代码：

const int N = 100010;
const int mod=1e9+7;

ll infast[N],fast[N];

ll qmi(ll x,ll p){
    ll res=1;
    while(p){
        if(p&1)res=res*x%mod;
        p>>=1;
        x=x*x%mod;
    }
    return res;
}

void init(int n){
    infast[0]=1;
    fast[0]=1;
    _fore(i,1,n){
        fast[i]=fast[i-1]*i%mod;
        infast[i]=qmi(fast[i],mod-2);
    }
}

void slove(){
   int n,k;
   cin>>n>>k;
   init(n);
   ll res=0;
   _fore(i,0,min(n,k)){
    res=(res+(fast[n]*infast[i]%mod)*infast[n-i]%mod)%mod;
   }
   cout << res << endl;
}