BZOJ3209 花神的数论题【组合数 + 按位计数】

题目

背景

众所周知，花神多年来凭借无边的神力狂虐各大 OJ、OI、CF、TC …… 当然也包括 CH 啦。

描述

话说花神这天又来讲课了。课后照例有超级难的神题啦…… 我等蒟蒻又遭殃了。

花神的题目是这样的

设 sum(i) 表示 i 的二进制表示中 1 的个数。给出一个正整数 N ，花神要问你

派(Sum(i)),也就是 sum(1)—sum(N) 的乘积。

输入格式

一个正整数 N。

输出格式

一个数，答案模 10000007 的值。

输入样例

输出样例

提示

对于样例一，112=2；

数据范围与约定

对于 100% 的数据，N≤10^15

题解

直接求太大，通过手算可以发现，由于乘法的交换律，我们可以把2放在一起，3放在一起，4放在一起........

就有\(ans = 1^{a1} + 2^{a2} + 3^{a3} + ....... + n^{an}\)

所以我们只需要求出包含特定数量1的数有多少个

但有一个上限N的限制，我们考虑递归计算

cal(u,v)表示u位【从高到低计算】及其之后放入v个1的合法方案

如果N的u位上是1，说明可以放1

如果放1，那么往下递归cal(u - 1,v - 1)

如果不放，之后\(u - 1\)位无论如何放，都不会大于N，所以就有\(C_{u - 1}^{v}\)中方案

最后累计出每一个指数，统计答案

现在考虑取模

值得一提的是，，\(1000007\)不是质数，它等于\(941 * 10627\)，所以我们不能用费马小定理

而应该用更一般的形式：\(a^{\phi(p)} \equiv 1 (mod p)\)，而\(\phi(10000007) = \phi(941) * \phi(10627) = 940 * 10626 = 9988440\)

那么指数运算时就模9988440就可以了

由于9988440不是质数，可能不存在逆元，组合数用递推式预处理出

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long int

#define REP(i,n) for (int i = 1; i <= (n); i++)

#define Redge(u) for (int k = h[u]; k; k = ed[k].nxt)

using namespace std;

const int maxn = 70,maxm = 100005,INF = 1000000000,P = 10000007,M = 9988440;

LL C[maxn][maxn],N,bit[maxn],n;

void init(){

	C[0][0] = 1;

	for (int i = 1; i < maxn; i++){

		C[i][0] = C[i][i] = 1;

		for (int j = 1; j <= (i >> 1); j++)

			C[i][j] = C[i][i - j] = (C[i - 1][j - 1] + C[i - 1][j]) % M;

	}

}

LL qpow(LL a,LL b){

	LL ans = 1;

	for (; b; b >>= 1,a = a * a % P)

		if (b & 1) ans = ans * a % P;

	return ans % P;

}

LL cal(int u,int v){

	if (!v) return 1;

	if (!u || u < v) return 0;

	if (!bit[u]) return cal(u - 1,v);

	return (C[u - 1][v] + cal(u - 1,v - 1)) % M;

}

int main(){

	init();

	cin >> N;

	for (n = 1; N; n++,N >>= 1)

		bit[n] = N & 1;

	n--;

	LL ans = 1;

	for (LL i = 1; i <= n; i++)

		ans = ans * qpow(i,cal(n,i)) % P;

	printf("%lld\n",(ans % P + P) % P);

	return 0;

}

花神