Welcome to the Digits Parade

2 secs 1024 MB
DivineJK's icon DivineJK

XX00以上2M2^M「以下」ですので、RR11であるかどうかで場合分けをする必要があります。

R1R\neq 1のとき、2M2^MXXの候補として考えられません。よって、00以上2M2^M未満の整数についてのみを考えればよいです。00以上2M2^M未満の整数は二進数で表すとMM桁(先頭の0を許す)です。 このMM桁の中で11である異なる桁をちょうどRR個選ぶ方法の数が答えとなるので、答えはMCR_ M\mathrm{C}_ Rです。 MMが大きくRRが小さいので、MCR=i=0R1Mii+1_ M\mathrm{C}_ R = \prod^{R-1}_ {i=0}\frac{M-i}{i+1}の式から計算できます。

R=1R=1のときは、2M2^MXXの候補として考えられるので、MC1+1=M+1_ M\mathrm{C}_ 1+1=M+1が答えです。