## 【HDU 4349】Xiao Ming’s Hope

### 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】序列统计

### 题解

ps：因为懒到不想写latex，所以化简过程让我们去膜拜Menci

### 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];

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();
printf("%d\n",(C(r-l+1,n+r-l+1)-1+MOD)%MOD);
}
return 0;
}


## 【HDU 3037】Saving Beans

lucas定理 + 插板法

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

const int MAXN = 100000+9;

int f[MAXN];

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


http://www.cnblogs.com/jianglangcaijin/p/3446839.html