Powered by:NEFU AB-IN

Link

3588. 排列与二进制

• 题意

  在组合数学中，我们学过排列数。
  从 n 个不同元素中取出 m（m<=n）个元素的所有排列的个数，叫做从 n 中取 m 的排列数，记为 p(n,m)。
  具体计算方法为 p(n,m)=n(n−1)(n−2)……(n−m+1)=n!/(n−m)!（规定 0!=1）。
  当 n 和 m 不是很小时，这个排列数是比较大的数值，比如 p(10,5)=30240。
  如果用二进制表示为 p(10,5)=30240=(111011000100000)b，也就是说，最后面有 5 个零。
  我们的问题就是，给定一个排列数，算出其二进制表示的后面有多少个连续的零。

• 思路

  求十进制后面多少个0，就是除以10，那么二进制就是同理，求有多少个2即可

  也就是求 $\frac{n!}{(n-m)!}$有多少个2

  两种做法：

  • 朴素做法 $O(n^2)$
    从$n-m+1$ 遍历到$n$，看每个数包含多少2
  • 优化做法 $O(logn)$
    阶乘分解即可

    定理: n的阶乘包含x个质因子p的数量
    $x=\frac{n}{p}+\frac{n}{p^2}+...$

• 代码

  朴素做法

  /* * @Author: NEFU AB-IN * @Date: 2022-07-30 00:39:09 * @FilePath: \Acwing\3588\3588.cpp * @LastEditTime: 2022-07-30 02:07:06 */
  #include <bits/stdc++.h>
  using namespace std;
  #define int long long
  #define SZ(X) ((int)(X).size())
  #define IOS \ ios::sync_with_stdio(false); \ cin.tie(0); \ cout.tie(0)
  #define DEBUG(X) cout << #X << ": " << X << '\n'
  typedef pair<int, int> PII;
  
  const int INF = INT_MAX;
  const int N = 1e6 + 10;
  
  signed main()
  {
        
      IOS;
      int n, m;
  
      function<int(int)> cale = [&](int x) {
        
          int cnt = 0;
          while (!(x & 1))
          {
        
              x >>= 1;
              cnt++;
          }
  
          return cnt;
      };
  
      while (cin >> n >> m, n != 0 && m != 0)
      {
        
          int ans = 0;
  
          for (int i = n - m + 1; i <= n; ++i)
          {
        
              ans += cale(i);
          }
          cout << ans << '\n';
      }
  
      return 0;
  }
  

  优化做法

  /* * @Author: NEFU AB-IN * @Date: 2022-07-30 00:39:09 * @FilePath: \Acwing\3588\tempCodeRunnerFile.cpp * @LastEditTime: 2022-07-30 12:32:14 */
  #include <bits/stdc++.h>
  using namespace std;
  #define int long long
  #define SZ(X) ((int)(X).size())
  #define IOS \ ios::sync_with_stdio(false); \ cin.tie(0); \ cout.tie(0)
  #define DEBUG(X) cout << #X << ": " << X << '\n'
  typedef pair<int, int> PII;
  
  const int INF = INT_MAX;
  const int N = 1e6 + 10;
  
  signed main()
  {
        
      IOS;
      int n, m;
  
      function<int(int, int)> cale = [&](int x, int p) {
        
          int cnt = 0;
          while (x)
              cnt += x /= p;
          return cnt;
      };
  
      while (cin >> n >> m, n != 0 && m != 0)
      {
        
          cout << cale(n, 2) - cale(n - m, 2) << '\n';
      }
  
      return 0;
  }