「SCOI2012」Blinker的仰慕者 - 数位动规

题目大意

    Blinker 有非常多的仰慕者，他给每个仰慕者一个正整数编号。而且这些编号还隐藏着特殊的意义，即编号的各位数字之积表示这名仰慕者对Blinker的重要度。
    现在Blinker想知道编号介于某两个值$A,B$之间，且重要度为某个定值$K$的仰慕者编号和。

---

题目分析

考试的时候写的状态与$K$有关，只能拿到$50$分，然而由于MLE的原因成功得到了$0$分的好成绩。

当$K\neq0$ 时：
由于$K$一定是由素数$2,3,5,7$组成的，否则无解，因此合法的$K$的数目不多，经搜索发现只有$40000+$个。
将所有的$K$进行按照$2,3,5,7$拆分，给每个拆分后的状态一个编号$id$。
故可以设置状态$f(i,j)$表示当第$i$位（从低位到高位），状态编号是$j$时，$f(i,j).first$表示合法的仰慕者个数，$f(i,j).second$表示编号和。
考虑转移，根据每个素数个数的减少即可转移，再结合仰慕者个数可以转移掉编号和。

当$K=0$ 时，就是一个简单的数位动规了，若某一位出现了$0$即合法。

自认为代码还是挺可读的。

---

代码

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;
#define pii pair<LL,LL>

inline LL Get_Int() {
	LL num=0,bj=1;
	char x=getchar();
	while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
	while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
	return num*bj;
}

const int pr[]= {2,3,5,7},maxs=50005,mod=20120427;

int count(int x,int k) {int cnt=0;while(x%k==0)x/=k,cnt++;return cnt;}

struct node {
	int len,cnt[4];
	node(int a=0,int b=0,int c=0,int d=0,int e=0) {len=a,cnt[0]=b,cnt[1]=c,cnt[2]=d,cnt[3]=e;}
};

LL Pow[20];
int idx[65][40][30][25],trans[maxs][10],tot=0;

void init() {
	Pow[0]=1;
	for(int i=1; i<=18; i++)Pow[i]=Pow[i-1]*10%mod;
	int cnt[10][4];
	for(int i=1; i<=9; i++)
		for(int p=0; p<4; p++)
			cnt[i][p]=count(i,pr[p]);
	queue<node> Q;
	Q.push(node());
	idx[0][0][0][0]=++tot;
	while(!Q.empty()) {
		node Now=Q.front();
		Q.pop();
		int id=idx[Now.cnt[0]][Now.cnt[1]][Now.cnt[2]][Now.cnt[3]];
		trans[id][0]=id;
		if(Now.len>18)continue;
		for(int i=1; i<=9; i++) {
			node Next=node(Now.len+1,Now.cnt[0]+cnt[i][0],Now.cnt[1]+cnt[i][1],Now.cnt[2]+cnt[i][2],Now.cnt[3]+cnt[i][3]);
			int &nid=idx[Next.cnt[0]][Next.cnt[1]][Next.cnt[2]][Next.cnt[3]];
			if(!nid) {nid=++tot;Q.push(Next);}
			trans[nid][i]=id;
		}
	}
}

int a[20];

int index(LL k) {
	int cnt[]= {0,0,0,0};
	for(int i=0; i<4; i++)while(k%pr[i]==0)k/=pr[i],cnt[i]++;
	if(k>1)return 0;
	return idx[cnt[0]][cnt[1]][cnt[2]][cnt[3]];
}

namespace notzero {
	pii f[20][maxs][2];
	bool vst[20][maxs][2];
	pii Dp(int Now,int s,bool zero,bool up) {
		if(Now==0)return pii(s==idx[0][0][0][0],0);
		if(!up&&vst[Now][s][zero])return f[Now][s][zero];
		if(!up)vst[Now][s][zero]=1;
		int lim=up?a[Now]:9;
		pii now(0,0);
		for(int i=!zero; i<=lim; i++) {
			pii next=Dp(Now-1,trans[s][i],zero&&i==0,up&&i==lim);
			now.first=(now.first+next.first)%mod;
			now.second=(now.second+next.second+i*Pow[Now-1]%mod*next.first%mod)%mod;
		}
		if(!up)f[Now][s][zero]=now;
		return now;
	}
}

namespace zero {
	pii f[20][2][2];
	bool vst[20][2][2];
	pii Dp(int Now,bool have,bool zero,bool up) {
		if(Now==0)return pii(have,0);
		if(!up&&vst[Now][have][zero])return f[Now][have][zero];
		if(!up)vst[Now][have][zero]=1;
		int lim=up?a[Now]:9;
		pii now(0,0);
		for(int i=0; i<=lim; i++) {
			pii next=Dp(Now-1,!zero&&(have||i==0),zero&&i==0,up&&i==lim);
			now.first=(now.first+next.first)%mod;
			now.second=(now.second+next.second+i*Pow[Now-1]%mod*next.first%mod)%mod;
		}
		if(!up)f[Now][have][zero]=now;
		return now;
	}
}

LL Solve(LL x,LL k) {
	if(k==0) {
		int cnt=0;
		while(x) {a[++cnt]=x%10;x/=10;}
		return zero::Dp(cnt,0,1,1).second;
	} else {
		int id=index(k),cnt=0;
		if(!id)return 0;
		while(x) {a[++cnt]=x%10;x/=10;}
		return notzero::Dp(cnt,id,1,1).second;
	}
}

int main() {
	init();
	int t=Get_Int();
	while(t--) {
		LL L=Get_Int(),R=Get_Int(),k=Get_Int();
		printf("%lld\n",(Solve(R,k)-Solve(L-1,k)+mod)%mod);
	}
	return 0;
}