51Nod 1048 整数分解为2的幂 V2

分析：

$O(N)$和$O(NlogN)$的做法很简单就不写了...%了一发神奇的$O(log^3n*$高精度$)$的做法...

考虑我们只能用$2$的整次幂来划分$n$，所以我们从二进制的方面去考虑划分...

定义$g[i][j]$代表的是前$i$个$1$划分完成并且最大的数为$2^j$的方案数，我们枚举前$i-1$个$1$的划分方案来转移：

$g[i][j]=\sum _{k=0}^{j} g[i-1][k]*f[x-k][j-k]$，$x$代表的是第$i$个$1$在第$x$位，$f[i][j]$代表$2^i$的划分方案，并且最大的数字为$2^j$，因为我们要限制$2^x$的划分必须比$2^k$大，所以我们把$2^x$和$2^j$都除以一个$2^k$...

然后$f$数组的转移也是差不多的...

$f[i][j]=\sum_{k=0}^{j} f[i-1][k]*f[i-k-1][j-k]$...

我的高精度写的常数贼大~~~

就当我A了吧...

代码：

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

//by NeighThorn

using namespace std;

const int maxn=100+5,maxm=200+5,mod=1e9;

int tmp;

char s[maxn];

struct M{

	int len,a[maxm],b[maxm];

	inline void init(void){

		memset(a,0,sizeof(a));

	}

	friend M operator + (M x,M y){

		M res;res.len=max(x.len,y.len);res.init();

		for(int i=1;i<=res.len;i++){

			res.a[i]+=x.a[i]+y.a[i];

			if(res.a[i]>=mod)

				res.a[i+1]=1,res.a[i]-=mod;

		}

		if(res.a[res.len+1]>0) res.len++;

		return res;

	}

	friend M operator * (M x,M y){

		M res;res.init();

		for(int i=1;i<=x.len;i++)

			for(int j=1;j<=y.len;j++){

				res.a[i+j]+=(res.a[i+j-1]+1LL*x.a[i]*y.a[j])/mod;

				res.a[i+j-1]=(res.a[i+j-1]+1LL*x.a[i]*y.a[j])%mod;

			}

		res.len=x.len+y.len;

		while(res.len>1&&res.a[res.len]==0) res.len--;

		return res;

	}

	inline void print(void){

		memcpy(b,a,sizeof(a));

		printf("%d",a[len]);

		for(int i=len-1;i;i--)

			for(int j=1e8;j;j/=10)

				printf("%d",a[i]/j),a[i]%=j;

		memcpy(b,a,sizeof(b));

		puts("");

	}

}n,m,ans,f[maxn][maxn],g[maxn][maxn];

signed main(void){

	scanf("%s",s);tmp=n.len=strlen(s);n.len=tmp/9+1;

	for(int i=1,j;i<=tmp;i++){

		j=(tmp-i)/9;

		n.a[j+1]=n.a[j+1]*10+s[i-1]-'0';

	}

	f[0][0].a[1]=1;f[0][0].len=1;

	for(int i=1;i<=99;i++){

		f[i][i].a[1]=1;f[i][i].len=1;

		for(int j=0;j<i;j++)

			for(int k=0;k<=j;k++)

				f[i][j]=f[i][j]+f[i-1][k]*f[i-1-k][j-k];

	}

	int tot=0;

	for(int i=0;i<=99;i++){

		if(n.a[1]&1){

			tot++;

			if(tot==1)

				for(int j=0;j<=i;j++)

					g[tot][j]=f[i][j];

			else

				for(int j=0;j<=i;j++)

					for(int k=0;k<=j;k++)

						g[tot][j]=g[tot][j]+g[tot-1][k]*f[i-k][j-k];

		}

		int lala=0;

		for(int j=n.len;j;j--){

			int tmp=n.a[j];

			n.a[j]=(1LL*lala*mod+tmp)/2;

			lala=(1LL*lala*mod+tmp)%2;

		}

	}

	for(int i=0;i<=99;i++) ans=ans+g[tot][i];

	ans.print();

	return 0;

}

By NeighThorn

巴特西

51Nod 1048 整数分解为2的幂 V2

分析：

代码：

最新文章

热门文章