此博客停更

开坑了！没怎么做过这类数位的题，总之不能因为我懒不熟练就不做，坑连着开真爽

由于懒找题能力有限，找不到太多这样的题，所以就挖小点的坑吧

现在几道：   2/4

bzoj3679 发现可能的乘起来的数不多，于是直接拿下标DP就行了

#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
#define ll long long
#define nc() getchar()
inline ll read(){
	ll x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
	for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
int cnt,i,k,m,j,n,x,y,z;ll o,l,r,f[100100],d[20][10010],s[20][10010];
#define up(k) upper_bound(f+1,f+cnt+1,k)
inline ll work(ll x){
	ll ret=0,y=x;int len=0,n=::n;
	while(y)++len,y/=10;
	for(i=1;i<len;++i)ret+=s[i][up(n)-f-1];
	while(len){
		int now=x/pow(10,len-1);
		for(int i=1;i<now;++i)if(n>=i)if(len>1)ret+=s[len-1][up(n/i)-f-1];else ++ret;
		if(now)n/=now;else break;x%=(ll)pow(10,len-1),--len;
	}
	return ret;
}
int main(){
	for(n=read(),l=read(),r=read(),i=0;i<=32;++i)for(j=0;j<=19;++j)for(k=0;k<=16;++k)for(z=0;z<=11;++z){
		o=1ll*pow(2,i)*pow(3,j)*pow(5,k)*pow(7,z);
		if(o<=n&&o>0)f[++cnt]=o;
	}
	for(sort(f+1,f+cnt+1),s[1][0]=0,i=1;i<=9;++i)d[1][i]=1;
	for(j=1;j<=cnt;++j)s[1][j]=s[1][j-1]+d[1][j];
	for(i=2;i<=18;++i){
		for(j=1;j<=up(pow(10,i))-f-1;++j)for(k=1;k<=9;++k)if(f[j]%k==0)d[i][j]+=d[i-1][lower_bound(f+1,f+cnt+1,f[j]/k)-f];
		for(s[i][0]=0,j=1;j<=cnt;++j)s[i][j]=s[i][j-1]+d[i][j];
	}
	printf("%lld\n",work(r)-work(l));
}

bzoj3329 _(:зゝ∠)_我刚开始不会做，看了$Claris$的题解发现很傻_(:зゝ∠)_，题傻，我更傻

#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define nc() getchar()
#define ll long long
inline ll read(){
	ll x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
	for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
#define mo 1000000007
ll i,j,k,m,n,x,y,f[77][2][2],T,cnt,a[77];
struct Mat{
	ll a[2][2];Mat(){a[0][1]=a[0][0]=a[1][0]=a[1][1]=0;}
	Mat operator *(const Mat&b){
		Mat ret;
		for(int i=0,j,k;i<=1;++i)
			for(j=0;j<=1;++j)for(k=0;k<=1;++k)(ret.a[i][j]+=a[i][k]*b.a[k][j])%=mo;
		return ret;
	}
}A,B,C;
int main(){
	for(T=read();T--;){
		for(y=x=read(),cnt=0;y;a[++cnt]=y&1ll,y>>=1ll);
		for(i=1,j=cnt;i<=cnt&&i<j;++i,--j)swap(a[i],a[j]);
		for(memset(f,0,sizeof f),i=0;i<=1;++i)f[1][i][i==a[1]]=1;
		for(i=1;i<cnt;++i){
			if(f[i][0][0])for(j=0;j<=1;++j)f[i+1][j][0]+=f[i][0][0];
			if(f[i][1][0])f[i+1][0][0]+=f[i][1][0];
			if(f[i][0][1])for(j=0;j<=a[i+1];++j)f[i+1][j][j==a[i+1]]+=f[i][0][1];
			if(f[i][1][1])f[i+1][0][0==a[i+1]]+=f[i][1][1];
		}
		printf("%lld\n",f[cnt][0][0]+f[cnt][1][0]+f[cnt][0][1]+f[cnt][1][1]-1);
		for(A=B=C=Mat(),A.a[0][1]=A.a[1][0]=A.a[1][1]=B.a[0][0]=C.a[0][0]=C.a[1][1]=1,B.a[1][0]=2;x;x>>=1ll,A=A*A)if(x&1ll)C=C*A;
		C=C*B,printf("%lld\n",C.a[0][0]);
	}
}

updating...