前言：
有些虚高，建议降蓝。感觉比 CF55D 要简单。
题目大意：
定义一个数为好数，满足以下要求：
-
每个数位都能整除原数。
-
每个数位都小于等于 \(6\)。
求长度为 \(n\) 的好数有多少个。
思路：
首先，\(0\) 整除任何数都没有意义，可以不枚举。其次，要满足条件二，所以每个数位可以只枚举 \(1 \sim 6\)。对于每个数位要整除原数，相当于所有数位的 lcm 必须整除原数。所以我选择对原数模 \(1 \sim 9\) 的 lcm 即 \(2520\)，可以保证条件一的正确性,并减少 dp 的内存需要。
即使如此，$40 \times 2520 \times 2520 $ 的内存仍然可能获得 MLE 的好成绩。（笔者没试）
但 \(1 \sim 2520\) 不都是我们需要的，我们只需要 \(1 \sim 9\) 可能组成的 lcm，所以可以离散化需要的 lcm，减少内存到 \(40 \times 2520 \times 50\)。这样再套个数位 dp 的记搜板子就能过了。
哦对了，仔细看看模数。
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define TP template<typename T>
#define TP_ template<typename T,typename ... T_>
TP void read(T &x)
{
x=0;int f=0;char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar())ch=='-'&&(f=1);
for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
f&&(x=-x);
}
TP_ void read(T &x,T_&...y){read(x);read(y...);}
TP void write(T x){x<0&&(putchar('-'),x=-x);static int sta[35];int top=0;do{sta[++top]=x%10,x/=10;}while(x);while(top)putchar(sta[top--]^48);}
TP void writeln(const T x){write(x);puts("");}
TP void writesp(const T x){write(x);putchar(32);}
TP_ void writeln(const T x,T_ ...y){writesp(x);writeln(y...);}
using LL=long long;
constexpr int N=50;
constexpr int B=10;
constexpr int P=1e6+7;
constexpr int mod=2520;
LL dp[N][mod][N],ma[mod+1];
LL n;
LL gcd(LL a,LL b){return !b?a:gcd(b,a%b);}
LL lcm(LL a,LL b){return !b?a:a/gcd(a,b)*b;}
LL dfs(int pos,int sum,int Lcm)
{
if(!pos)return sum%Lcm==0;
if(~dp[pos][sum][ma[Lcm]])return dp[pos][sum][ma[Lcm]];
LL res=0,up=6;
for(int i=1;i<=up;i++)
res=(res+dfs(pos-1,(sum*10+i)%mod,lcm(Lcm,i)))%P;
return dp[pos][sum][ma[Lcm]]=res;
}
LL calc(int n){return dfs(n,0,1);}
void prepare()
{
memset(dp,-1,sizeof(dp));
int cnt=0;
for(int i=1;i<=mod;i++)
if(mod%i==0)
ma[i]=++cnt;
}
int main()
{
prepare();
int T;read(T);
while(T--)
read(n),
writeln(calc(n));
return 0;
}