【HDU 4349】Xiao Ming’s Hope

相关链接

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=4349
神犇题解:http://blog.csdn.net/u013486414/article/details/48130553

题目大意

求${n \choose i},i \in [1,n]$中有多少个奇数
其中$n \le 10^{18}$

解题报告

原题相当于求${n \choose i} \% 2$有多少个为$1$
考虑使用$Lucas$定理,将模数设为$2$
此时相当于把$n,i$都转成了二进制下,然后单独考虑每一位
因为${1 \choose 1} = {1 \choose 0} = {0 \choose 0} = 1,{0 \choose 1} = 0$
所以当$n$的那个二进制位为$1$的时候,$i$那一位可以为$0/1$,但当$n$那一位为$0$时,$i$只能为$0$
所以最终方案数为$2^{\sum\limits_{i=0}^{63}{(n>>i) \& 1}}$

Code

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

int main() {
	for (LL n,ans;~scanf("%I64d",&n);){
		ans = pow(2, __builtin_popcountll(n)) + 0.5;
		cout<<ans<<endl;
	}
	return 0;
}

【BZOJ 4403】序列统计

链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4403
神犇题解:https://oi.men.ci/bzoj-4403/

题解

因为数定了,其单调不降的序列也就定了
所以这题就是求\(\sum\limits_{L = 1}^n {C_{r – l + L}^{r – l}} \)
然后化简一下就得到最终答案为:C(r-l+1,n+r-l+1)-1
ps:因为懒到不想写latex,所以化简过程让我们去膜拜Menci
因为n,l,r都巨大,所以用lucas定理来求组合数

Code

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

const int N = 1000000+9;
const int MX = 1000000+2; 
const int MOD = 1000000+3;

int T,POW[N],REV[N];

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline int pow(int w, int t) {
	int ret = 1;
	while (t) {
		if (t & 1) ret = (LL)ret * w % MOD;
		w = (LL)w * w % MOD; t >>= 1;
	}
	return ret;
}

inline void prework() {
	POW[0] = REV[0] = 1;
	for (int i=1;i<=MX;i++) 
		POW[i] = (LL)POW[i-1] * i % MOD;
	REV[MX] = pow(POW[MX], MOD - 2);
	for (int i=MX-1;i;i--) 
		REV[i] = (LL)REV[i+1] * (i+1) % MOD;
}

int C(int a, int b) {
	if (a > b) return 0;
	else if (b <= MX) {
		return (LL)POW[b] * REV[a] * REV[b-a] % MOD;
	} else {
		return (LL)C(a%MOD, b%MOD) * C(a/MOD, b/MOD) % MOD;
	}
}

int main(){
	prework();
	for (int T=read(),n,l,r;T;T--) {
		n = read(); l = read(); r = read();
		printf("%d\n",(C(r-l+1,n+r-l+1)-1+MOD)%MOD);
	}
	return 0;
}

【HDU 3037】Saving Beans

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=3037
数据生成器:http://paste.ubuntu.com/22886753/

lucas定理 + 插板法

#include<iostream>
#include<cstdio>
#define LL long long
using namespace std;

const int MAXN = 100000+9;

int f[MAXN];

inline int read(){
	char c=getchar(); int ret=0;
	while (c<'0'||c>'9') c=getchar();
	while (c<='9'&&c>='0') ret=ret*10+c-'0', c=getchar();
	return ret;	
}

inline int quick_pow(int w, int t, int p) {
	int ret = 1;
	while (t) {
		if (t & 1) ret = (LL)ret*w % p;
		w = (LL)w*w % p; t >>= 1;
	}
	return ret;
}

inline int C(int m,int n, int p) {
	if (n > m) return 0;
	else return (LL)f[m]*quick_pow(f[m-n],p-2,p)*quick_pow(f[n],p-2,p)%p;
}

int lucas(int m, int n, int p) {
	if (n == 0) return 1;
	else return ((LL)lucas(m/p,n/p,p) * C(m%p,n%p,p)) % p;
}

int main(){
	int T = read(); while (T--) {
		int n = read(),m = read(),p = read(); 
		f[0] = 1; for (int i=1;i<=p;i++) f[i] = (LL)f[i-1]*i % p;
		printf("%d\n",lucas(n+m,n,p));
	}
	return 0;
}

另外,lucas定理可以推广到整数域上,参见:
http://www.cnblogs.com/jianglangcaijin/p/3446839.html