BZOJ 3209 花神的数论题

Link

Solution

就是枚举有多少个1求有多少个含有这些个1的数字。。 然后一开始在Windows计算器上看1e15是几位数,结果可能是少看了几个0少算了几位然后数组开小了然后T飞了然后本地还一切正常 指数不会爆long long,可以直接不膜。如果一定要膜,需要膜\(\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? 负数吗??

Powered by Hexo and Hexo-theme-hiker

Copyright © 2013 - 2017 Hey,Lucida here. All Rights Reserved.

Lucida Lu 保留所有权利