首页 > 代码库 > BZOJ3209: 花神的数论题

BZOJ3209: 花神的数论题

2024-07-19 03:47:51   214人阅读

3209: 花神的数论题

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 689  Solved: 334
[Submit][Status]

Description

背景
众所周知，花神多年来凭借无边的神力狂虐各大 OJ、OI、CF、TC …… 当然也包括 CH 啦。
描述
话说花神这天又来讲课了。课后照例有超级难的神题啦…… 我等蒟蒻又遭殃了。
花神的题目是这样的
设 sum(i) 表示 i 的二进制表示中 1 的个数。给出一个正整数 N ，花神要问你
派(Sum(i)),也就是 sum(1)—sum(N) 的乘积。

 

Input

一个正整数 N。

 

Output

一个数，答案模 10000007 的值。

 

Sample Input

样例输入一

3

Sample Output

样例输出一

2

HINT

 



对于样例一，1*1*2=2；


数据范围与约定


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

 

Source

原创 Memphis

题解：
晚上做题各种不爽，明明想出了正解，一直WA，等A了在写题解吧。。。
代码：
1.自己yy的，虽然慢，但AC没问题
 1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #define inf 100000000012 #define maxn 10013 #define maxm 500+10014 #define mod 1000000715 #define ll long long16 #define pa pair<int,int>17 using namespace std;18 ll ans,n,c[maxn][maxn],tot,sum,a[maxn];19 ll power(ll x,ll y)20 {21     ll t;22     for(t=1;y;y>>=1,x*=x,x%=mod)23      if(y&1){t*=x;t%=mod;}24     return t; 25 }26 ll dp(int sum,int x)27 {28     ll t=1,w;29     for(int i=0;i<=x;i++)30      {31       w=power(sum+i,c[x][i]);32       if(w)t*=w,t%=mod;33      } 34     return t;35 }36 int main()37 {38     freopen("input.txt","r",stdin);39     freopen("output.txt","w",stdout);40     while(cin>>n)41     {42     tot=0;43     c[0][0]=1;44     for(int i=1;i<=64;i++)45      {46          c[i][0]=1;c[i][i]=1;47          for(int j=1;j<=i-1;j++)c[i][j]=(c[i-1][j-1]+c[i-1][j])% mod;48      }49     while(n){a[++tot]=n%2;n>>=1;}50     ans=1;sum=0;51     for(int i=tot;i>0;i--)52     if(a[i])53      {54       ans*=dp(sum,i-1);ans%=mod;sum++;55      }56     ans*=sum;ans%=mod;57     printf("%lld\n",ans);58     }59     return 0;60 }
View Code

 

2.网上的，自己抄都不对？

 1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #define inf 100000000012 #define maxn 10013 #define maxm 500+10014 #define mod 1000000715 #define ll long long16 #define pa pair<int,int>17 using namespace std;18 ll ans,n,c[maxn][maxn],tot,sum,a[maxn];19 ll power(ll x,ll y)20 {21     ll t;22     for(t=1;y;y>>=1,x*=x,x%=mod)23      if(y&1){t*=x;t%=mod;}24     return t; 25 }26 ll calc(int x)27 {28    ll t=0;29    for(int i=tot;i&&x>=0;i--)30     if(a[i])t+=c[i-1][x--];31    return t;32 }33 int main()34 {35     freopen("input.txt","r",stdin);36     freopen("output.txt","w",stdout);37     while(cin>>n)38     {39     n++;    40     tot=0;41     c[0][0]=1;42     for(int i=1;i<=64;i++)43      {44          c[i][0]=1;c[i][i]=1;45          for(int j=1;j<=i-1;j++)c[i][j]=(c[i-1][j-1]+c[i-1][j])% mod;46      }47     while(n){a[++tot]=n%2;n>>=1;}48     ans=1;49     for(int i=1;i<=tot;i++)ans*=power(i,calc(i)),ans%=mod;50     printf("%lld\n",ans);51     }52     return 0;53 }
View Code

 

BZOJ3209: 花神的数论题


联系
我们