程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> bzoj 3209 花神的數論題（數位dp）

bzoj 3209 花神的數論題（數位dp）

編輯：C++入門知識

bzoj 3209 花神的數論題（數位dp）

3209: 花神的數論題

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 980 Solved: 460
[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

思路：數位dp，對於二進制i這一位如果是1，那麼後面有i-1位置可以填1或0，就可以知道新增加了多少個1，需要注意的是要記錄這個數前面已經出現了幾個1

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include


#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define MID(x,y) ((x+y)>>1)

#define eps 1e-8
typedef long long ll;

#define fre(i,a,b)  for(i = a; i < b; i++)
#define mem(t, v)   memset ((t) , v, sizeof(t))
#define sf(n)       scanf("%d", &n)
#define sff(a,b)    scanf("%d %d", &a, &b)
#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
#define pf          printf
#define bug         pf("Hi\n")

using namespace std;
#define mod 10000007

#define INF 0x3f3f3f3f
#define N 60

ll C[N][N]; //組合數
ll a[N];
ll n;
ll len;

void inint()
{
	int i,j;
	C[0][0]=1;
	fre(i,1,N)
	{
		C[i][0]=1;
		fre(j,1,i)
		  {
		  	C[i][j]=C[i-1][j]+C[i-1][j-1];
		  }
		C[i][i]=1;
	}

}

void solve()
{
  int bit[N];
  int len=0;
  while(n)
  {
  	bit[++len]=n%2;
  	n>>=1;
  }

  int now=0;
  int i,j;

  for(i=len;i>=1;i--)
	if(bit[i])
  {
  	 for(j=0;j0)
	{
		if(y&1) ans=ans*x%mod;
		y>>=1;
		x=x*x%mod;
	}
	return ans;
}

int main()
{
    inint();

    int i;
    scanf("%lld",&n);
	mem(a,0);
	n++;
	solve();
	ll ans=1;

	fre(i,1,N)
		ans=ans*pow_(i,a[i])%mod;

	pf("%lld\n",ans);
	return 0;
}

記憶化代碼：

//dp[i][j]代表第i位取j會得到的所有1的位數積

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define MID(x,y) ((x+y)>>1)

#define eps 1e-8
typedef long long ll;

#define fre(i,a,b)  for(i = a; i < b; i++)
#define mem(t, v)   memset ((t) , v, sizeof(t))
#define sf(n)       scanf("%d", &n)
#define sff(a,b)    scanf("%d %d", &a, &b)
#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
#define pf          printf
#define bug         pf("Hi\n")

using namespace std;
#define mod 10000007

#define INF 0x3f3f3f3f
#define N 60

ll dp[N][N];
int bit[N];
ll n;

ll dfs(int pos,int n, bool bound)
{
    if(pos==0) return n ? n:1;

    if(!bound&&dp[pos][n]!=-1) return dp[pos][n];

    int up=bound? bit[pos]:1;
    ll ans=1;
    int i;
    fre(i,0,up+1)
    {
       if(i==0)
			ans*=dfs(pos-1,n,bound&&i==up);
	   else
		    ans*=dfs(pos-1,n+1,bound&&i==up);
	   if(ans>=mod)
		 ans%=mod;
    }
   if(!bound)
	dp[pos][n]=ans;
   return ans;
}

ll solve()
{
	int i,len=0;
	while(n)
	{
		bit[++len]=n%2;
		n>>=1;
	}
   return dfs(len,0,true)%mod;
}

int main()
{
	mem(dp,-1);

	scanf("%lld",&n);
	printf("%lld\n",solve());
	return 0;
}