BZOJ 3209 花神的数论题

发表于 | 更新于

Link

Solution

就是枚举有多少个1求有多少个含有这些个1的数字。。 然后一开始在Windows计算器上看1e15是几位数，结果可能是少看了几个0少算了几位然后数组开小了然后T飞了然后本地还一切正常 指数不会爆long long，可以直接不膜。如果一定要膜，需要膜φ(p)\varphi(p)。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include "lucida"

const int P=10000007,Phi=9988440,B=50,MAXB=B+5;
int64 C[MAXB][MAXB];
void Prep() {
	C[0][0]=1;
	for(int i=1;i<=B;++i) {
		C[i][0]=1;
		for(int j=1;j<=i;++j)
			C[i][j]=(C[i-1][j-1]+C[i-1][j])%Phi;
	}
}
int bit[MAXB],len;
int64 Cal(int k) {
	int64 res=0;
	for(int i=len,cnt=0;i;--i)
		if(bit[i]) {
			(res+=C[i-1][k-cnt])%=Phi;
			if(k+1==++cnt)
				break;
		}
	return res;
}
int64 Pow(int64 base,int64 index) {
	int64 res=1;
	for(;index;(base*=base)%=P,index>>=1)
		if(index&1) (res*=base)%=P;
	return res;
}
int main() {
	freopen("input","r",stdin);
	Prep();
	int64 n,x;is>>n;
	for(len=0,x=n+1;x;x>>=1)
		bit[++len]=x&1;
	bit[len+1]=0;
	int64 Ans=1;
	for(int i=1;i<=len;++i)
		(Ans*=Pow(i,Cal(i)))%=P;
	os<<Ans<<'\n';
	return 0;
}
//TLE? 负数吗？？