[数据结构与算法]Gym 103443L Leadfoot 二进制+组合数数论 神仙题

题意

有很多人进行一场比赛，比赛是1v1的形式，不会平局，只有胜场和输场数完全相同的选手才能进行比赛，当胜场数到达$n$或者败场数到达$m$时,选手将不再参与比赛.比赛完全结束后,主办方将给所有比赛全败的选手颁发一个英勇不屈奖章,问最少要准备多少枚奖章.

题解

观察样例发现所有的答案肯定是$2$的某个幂,且$n,m$可以交换.再仔细思考,我们意识到当参赛的总人数是$2$的一个幂时,存在某种胜负场数的人数是奇数,此时参赛的总人数最少,准备的奖章数量也最少.显然这和杨辉三角有关,因此这既是一个二进制数论题也是一个组合数数论题.
再仔细分析,当一名选手以胜场数达到$n$结束比赛时,他的负场数为$i$,则这样的人数为$C_{p+i?1}^i$,满足这个数为奇数的条件$p>n+i?\_bp(n)?\_bp(i)+\_bp(n+i)$,其中$\_bp$为__builtin_popcount的简称.由于$n$为$10^6$,所以$i<n?20$时,上式便不能出现最大值,故只要暴力枚举$20$个$i$便可得到最优的结果,最后只要用简单的快速幂把答案算出来就好了.

const int yuzu=1e6,mod=1e9+7;
int main() {
  for (int t=read();t--;) {
    ll n,m,zw=0,i;
    #define _bp __builtin_popcount
    read(n),read(m),--n,--m;
    auto kasumi=[&](ll a,ll b=mod-2) {
      ll zw=1;
      for (;b;b>>=1,a=a*a%mod) if (b&1) zw=zw*a%mod;
      return zw;
    };
    for (i=max(0ll,m-20);i<=m;++i) zw=max(zw,n+i+1-_bp(n)-_bp(i)+_bp(n+i));
    printf("%lld\n",kasumi(2,zw-m-1));
  }
}

谢谢大家.