BZOJ 1183: [Croatian2008]Umnozak 数位dp

1183: [Croatian2008]Umnozak

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 95 Solved: 48
[Submit][Status][Discuss]

Description

定义一个数的digit-product是它的各个位上的数字的乘积,定义一个数的self-product是它本身乘以它的digit-pr oduct。编程求self-product在a和b之间的数的个数。

Input

两个整数a,b(1 ≤ a ≤ b < 10^18)。

Output

一个整数，self-product在a和b之间的数的个数。

Sample Input

145 192

Sample Output

这个题解就很棒了↓

http://blog.csdn.net/neither_nor/article/details/61210452

不过交愚蠢的副官的时候mle了

是习惯写调整法的锅 // 当然也懒得改

最后强行在数组上每一维-1的卡空间显然是不合理的

不过数据水能过..

#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<vector>
#include<string>
#include<bitset>
#include<queue>
#include<set>
#include<map>
using namespace std;

typedef long long ll;

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
void print(int x)
{if(x<0)putchar('-'),x=-x;if(x>=10)print(x/10);putchar(x%10+'0');}

const int son[10][4]={{0,0,0,0},{0,0,0,0},{1,0,0,0},{0,1,0,0},{2,0,0,0},{0,0,1,0},{1,1,0,0},{0,0,0,1},{3,0,0,0},{0,2,0,0}};

ll f[20][10][31][20][14][12];

void initial(int lim)
{
	register int bit,num,nt,i,j,k,o,a,b,c,d;
	for(num=1;num<10;++num)
		f[1][num][son[num][0]][son[num][1]][son[num][2]][son[num][3]]=1;
	for(bit=1;bit<19;++bit)
		for(num=1;num<10;++num)
			for(i=0,a=1;a<=lim;++i,a*=2)
				for(j=0,b=1;1ll*a*b<=lim;++j,b*=3)
					for(k=0,c=1;1ll*a*b*c<=lim;++k,c*=5)
						for(o=0,d=1;1ll*a*b*c*d<=lim;++o,d*=7)
							if(f[bit][num][i][j][k][o])
								for(nt=1;nt<10;++nt)
									if(i+son[nt][0]<31 && j+son[nt][1]<20 && k+son[nt][2]<14 && o+son[nt][3]<12)
										f[bit+1][nt][i+son[nt][0]][j+son[nt][1]][k+son[nt][2]][o+son[nt][3]]
										+=f[bit][num][i][j][k][o];
}

int st[20],top;

inline void get_lim(ll x)
{top=0;while(x){st[++top]=x%10;x/=10;}}

ll solve(ll lim,int I,int J,int K,int O)
{
	register int bit,num;
	get_lim(lim);
	ll res(0);
	for(bit=1;bit<top;++bit)
		for(num=1;num<10;++num)
			res+=f[bit][num][I][J][K][O];
	for(bit=top;bit;bit--)
	{
		for(num=1;num<st[bit]+(bit==1);++num)
			res+=f[bit][num][I][J][K][O];
		if(!st[bit]) break;
		I-=son[st[bit]][0];
		J-=son[st[bit]][1];
		K-=son[st[bit]][2];
		O-=son[st[bit]][3];
		if(I<0 || J<0 || K<0 || O<0) break;
	}
	return res;
}

int main()
{
	ll L,R;
	scanf("%lld%lld",&L,&R);
	ll ans(0);
	int lim=floor(sqrt(R));
	initial(lim);
	register int i,j,k,o,a,b,c,d,tmp;
	for(i=0,a=1;a<=lim;++i,a*=2)
		for(j=0,b=1;1ll*a*b<=lim;++j,b*=3)
			for(k=0,c=1;1ll*a*b*c<=lim;++k,c*=5)
				for(o=0,d=1;1ll*a*b*c*d<=lim;++o,d*=7)
				{
					tmp=a*b*c*d;
					ans+=solve(R/tmp,i,j,k,o);
					ans-=solve((L+tmp-1)/tmp-1,i,j,k,o);
				}
	cout<<ans<<endl;
}

秒客网