【BZOJ3209】花神的数论题 数位DP(我姿势不标准,但是可能更好写)

时间:2022-12-16 11:42:25

#include <stdio.h>
int main()
{
	puts("转载请注明出处谢谢");
	puts("http://blog.csdn.net/vmurder/article/details/43370607");
}


题解:

数位DP无疑。注:下面说的位基本都是二进制。

f[i][j]表示前i位数中有j个1的数的数量(包括0哦~)

然后一个低位数后面填0/1分别是两种向高位的转移,这样在O(log^2 n)时间内处理出f



主要是我的姿势(嗯,我叫它数位树):

    我是把一个大段像线段树一样分成一个个小段,一旦遇到一个完整的段就可以O(1)计数(这里是logn,因为是记录了有i个1的数的个数),然后不完整的就向下一位看,直到完整。


代码:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 200
#define MOD 10000007
using namespace std;
long long n,ans[N];
long long f[N][N],len;
long long power(long long x,long long k)
{
	long long ret=1;
	while(k)
	{
		if(k&1)ret=ret*x%MOD;
		x=x*x%MOD,k>>=1;
	}
	return ret;
}
void get(int have,long long x,int l)
{
	int i,j,k;
	if(x==1)ans[have+1]=(ans[have+1]+1)%MOD;
	if(x<=1)
	{
		ans[have]=(ans[have]+1)%MOD;	
		return ;
	}
	if(!l)return ;
	if(x>=(1<<l-1))for(i=0;i<=60;i++)ans[i+have]=(ans[i+have]+f[l-1][i])%MOD;
	if(x==(1<<l))for(i=0;i<=60;i++)ans[i+have+1]=(ans[i+have+1]+f[l-1][i])%MOD;
	else if(x<(1<<l-1))get(have,x,l-1);
	else get(have+1,x-(1<<l-1),l-1);
}
int main()
{
	int i,j,k;
	scanf("%lld",&n);
	while(n>>len)len++;
	for(i=0;i<=len;i++)
	{
		f[i][0]=1;
		for(j=1;j<=i;j++)f[i][j]=f[i-1][j-1]+f[i-1][j];
	}
	get(0,n,len);
	long long print=1;
	for(i=2;i<=60;i++)print=print*power(i,ans[i])%MOD;
	cout<<print<<endl;
	return 0;
}