[Submit][Status][Discuss]
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
[Submit][Status][Discuss]
好吧……這題一開始的范圍是N<=1015
然後我很天真的以為這不水嗎^?結果……
好吧……
之後要來數據以後才發現……
n<=10^15
只有我這種蒟蒻會被這個騙……
被各種D……
Ok，那麼這題就是數位統計了……
剛學的……（還在學這個<-弱）
[cpp]
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<cctype>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define RepD(i,n) for(int i=n;i>=0;i--)
#define MAXN (100000)
#define MAXL (50+10)
#define F (10000007)
int a[MAXN],len=0;
long long C[MAXL][MAXL];
long long n;
long long calc(int k)
{
long long ans=0;
ForD(i,len)
{
if (a[i])
{
ans+=C[i-1][k];
k--;
}
if (k<0) return ans;
}
return ans;
}
long long pow2(long long a,long long b)
{
if (b==0) return 1;
if (b==1) return a;
long long tmp=pow2(a,b/2);
tmp=tmp*tmp%F;
if (b%2) tmp=(tmp*a)%F;
return tmp;
}
int main()
{
// freopen("flower1.in","r",stdin);
// freopen(".out","w",stdout);
Rep(i,50)
{
C[i][0]=1;
For(j,i) C[i][j]=(C[i-1][j]+C[i-1][j-1]);
}
/*
cout<<pow2(2,1001)<<endl;
int pp=1;
For(i,1001) pp=(pp*2)%F;cout<<pp;
*/
while (cin>>n)
{
n++;//cout<<n<<endl;
len=0;
while (n) {a[++len]=n%2;n/=2;}
long long ans=1;//cout<<len<<endl;
For(i,len) ans=(ans*pow2(i,calc(i)))%F;
printf("%lld\n",ans);
};
return 0;
}
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<cctype>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define RepD(i,n) for(int i=n;i>=0;i--)
#define MAXN (100000)
#define MAXL (50+10)
#define F (10000007)
int a[MAXN],len=0;
long long C[MAXL][MAXL];
long long n;
long long calc(int k)
{
long long ans=0;
ForD(i,len)
{
if (a[i])
{
ans+=C[i-1][k];
k--;
}
if (k<0) return ans;
}
return ans;
}
long long pow2(long long a,long long b)
{
if (b==0) return 1;
if (b==1) return a;
long long tmp=pow2(a,b/2);
tmp=tmp*tmp%F;
if (b%2) tmp=(tmp*a)%F;
return tmp;
}
int main()
{
// freopen("flower1.in","r",stdin);
// freopen(".out","w",stdout);
Rep(i,50)
{
C[i][0]=1;
For(j,i) C[i][j]=(C[i-1][j]+C[i-1][j-1]);
}
/*
cout<<pow2(2,1001)<<endl;
int pp=1;
For(i,1001) pp=(pp*2)%F;cout<<pp;
*/
while (cin>>n)
{
n++;//cout<<n<<endl;
len=0;
while (n) {a[++len]=n%2;n/=2;}
long long ans=1;//cout<<len<<endl;
For(i,len) ans=(ans*pow2(i,calc(i)))%F;
printf("%lld\n",ans);
};
return 0;
}
