时间戳

首页 > 技术文章 > 自主命题：奇组合数个数统计

自主命题：奇组合数个数统计

Shimarin 2020-09-28 23:29 原文

Description

对于给定的数字\(n,l,r\)，求在 \(C_n^l,C_n^{l+1},C_n^{l+2},\dots,C_n^r\) 中共有多少个奇数。

行号\(n\)从0开始计数。特别地，我们规定\(C_0^0 = 1\)。

数据保证 \(0 \leq n \leq 10^{18}\)


Algorithm1: Divide and Conquer

拿到一个1e18的题，第一反应肯定是先打个表看看嘛。

我们知道有杨辉三角：

\[1\\ 1 \ \ \ 1\\ 1 \ \ \ 2 \ \ \ 1\\ 1 \ \ \ 3 \ \ \ 3 \ \ \ 1\\ 1 \ \ \ 4 \ \ \ 6 \ \ \ 4 \ \ \ 1\\ 1 \ \ \ 5 \ \ \ 10 \ \ \ 10 \ \ \ 5 \ \ \ 1\\ 1 \ \ \ 6 \ \ \ 15 \ \ \ 20 \ \ \ 15 \ \ \ 6 \ \ \ 1 \\ 1 \ \ \ 7 \ \ \ 21 \ \ \ 35 \ \ \ 35 \ \ \ 21 \ \ \ 7 \ \ \ 1 \\ \dots \ \ \ \ \ \ \ \dots \ \ \ \ \ \ \ \dots \]

我们把其中的奇数标成1，偶数标成0，于是得到：

\[1\\ 1 \ \ \ 1\\ 1 \ \ \ 0 \ \ \ 1\\ 1 \ \ \ 1 \ \ \ 1 \ \ \ 1\\ 1 \ \ \ 0 \ \ \ 0 \ \ \ 0 \ \ \ 1\\ 1 \ \ \ 1 \ \ \ 0 \ \ \ 0 \ \ \ 1 \ \ \ 1\\ 1 \ \ \ 0 \ \ \ 1 \ \ \ 0 \ \ \ 1 \ \ \ 0 \ \ \ 1 \\ 1 \ \ \ 1 \ \ \ 1 \ \ \ 1 \ \ \ 1 \ \ \ 1 \ \ \ 1 \ \ \ 1 \\ \dots \ \ \ \ \ \ \ \dots \ \ \ \ \ \ \ \dots \]

你也可以再列出一些，不过总之我们发现，这个01构成的三角形似乎有着某种绝佳的对称性。

实际上，这正是一种分形，名叫谢尔宾斯基三角形。


根据这种绝佳的对称性，我们容易设计出一种分治算法：

typedef long long ll;
ll solve(ll n, ll l, ll r)
{
	ll ret = 0, cnt_0, L, R;

	if(n == 0)			ret = 1;
	else
	{
		cnt_0 = powt(ceil(log2(n + 1))) - n - 1;
		R = (n + 1 - cnt_0) / 2 - 1;
		L = R + cnt_0 + 1;

		if(l <= R)	ret += solve(R, l, min(R, r));
		if(L <= r)	ret += solve(R, max(L, l) - L, r - L);
	}
	return ret;
}

我们用cnt_0统计所求行最中间0的个数，

R 表示将中间的0去掉后左侧部分的右端点，

L 表示将中间的0去掉后右侧部分的左端点。

然后分别向左右两侧递归地计算答案。

这种写法比较直观，但不是最优美简洁的。


该算法的复杂度分析是比较困难的，不过我们容易发现 \(n = 2 ^ t - 1\) 时是最坏的情况。

此时有 \(T(n) = 2 \times T(\frac{n}{2}) + log_2 n\)，复杂度是略大于\(O(n)\)的。

但经测试，在数据随机的背景下，\(n\) 在 1e11 的量级时该算法仍然有较好的表现。


平均复杂度的证明留给读者。


Algorithm2: Lucas' Theorem

求奇偶性，不就是求 \(mod\ 2\) 的值吗？

求组合数取模后的结果，不就是Lucas定理吗？

此外，利用上面的切尔宾斯基三角形其实也是证明Lucas定理的一种方法。

Lucas's Theorem:

\[\binom{x_1 \cdot p + y_1}{x_2 \cdot p + y_2} \equiv \binom{x_1}{x_2} \cdot \binom{y_1}{y_2} \ \ \ \ (mod \ \ p) \]

其中，

\[\binom{m}{n} = C_n^m \]

只是另一种表达方式罢了，只不过这样写更容易看清。

接下来我们考虑求 \(C_n^m \ mod \ 2\)，可以考虑对 \(C_n^m\) 连续使用Lucas定理。

我们将\(n, m\)两个数二进制表示：

\[n = \sum_{i = 0}^K a_i \cdot 2^i \\ m = \sum_{i = 0}^K b_i \cdot 2^i \]

这里 \(n,m\) 的二进制位数当然不一定相同，我们可以在最高位补0，效果相同。

那么我们有，

\[\binom{m}{n} \equiv \prod _ {i = 0} ^ K \binom{b_i}{a_i} \ \ \ \ (mod \ p) \]

如果 \(C_n^m\) 是奇数，那么右式就应当为得1，否则即为0。

而我们知道\(a_i, b_i\)的取值只有\(0, 1\)，又有：

\[\binom00 = 1,\ \binom01 = 1,\ \binom11 = 1,\ \binom10 = 0 \]

稍作观察就能发现：

\[\binom{m}{n} \ mod \ 2 = \cases{0 & m or n $\ne$ n\\1 & m or n = n} \]

由此，我们 \(O(n)\) 地枚举 \([l, r]\) 间的所有整数即可。

register long long cnt = 0;
for(register long long i = l; i <= r; ++i)
    cnt += ((i | n) == n);

代码就这。


Algorithm3: Dynamic Programing

可以发现我们用了一下Lucas定理之后平均复杂度可能还不如找规律。

这是因为我们枚举了 \([l, r]\) 间的所有整数的缘故。

但考虑现在的问题：求 \([l, r]\) 间或\(n\)得\(n\)的数的个数，这是一个容易解决的数位DP问题。

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
vector<bool> lim;
ll n, l, r, dp[64][2];

int len;
ll dfs(int ith, bool ful)
{
	if(ith == len) 		return 1;
	if(dp[ith][ful])	return dp[ith][ful];

	ll res = 0;
	if((1ll << (len - ith - 1)) & n)
	{
		if(lim[ith])
		{
			res += dfs(ith + 1, ful);
			res += dfs(ith + 1, false);
		}
		else
		{
			if(ful)	res += dfs(ith + 1, ful);
			else	res += 2 * dfs(ith + 1, ful);
		}
	}
	else	res += dfs(ith + 1, ful & (!lim[ith]));
	
	return dp[ith][ful] = res;
}

ll solve(ll x)
{
	if(x == -1)	return 0;
	
	lim.clear();
	memset(dp, 0, sizeof(dp));

	while(x) {
		lim.push_back(x & 1);
		x >>= 1;
	}
	len = lim.size();
	reverse(lim.begin(), lim.end());
	
	return dfs(0, true);
}

int main()
{
	freopen("math.in", "r", stdin);
	freopen("math.out", "w", stdout);
	cin >> n >> l >> r;
	cout << solve(r) - solve(l - 1) << endl;
	return 0;
}

复杂度是易于分析的\(O(logn)\)，证明留给读者。

推荐阅读