摘要
Title: 3588. 排列与二进制
Tag: 二进制、阶乘分解
Memory Limit: 64 MB
Time Limit: 1000 ms

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;
}

3588. 排列与二进制

题意

思路

代码