题目中的那个大数一定是若干个1+若干个2+若干个3...+若干个9组成的,显然可以转化成9个(underbrace {111...1}_{a_i个1}(0le a_1le a_2le a_3...le a_9,a_9=n))之和
然后模数只有500,所以可以考虑处理出所有(mod p =i)的不同长度的(111...1)个数记为(cnt_i),考虑dp求答案,设(f_{i,j,k})表示考虑了前(i)个剩余类,用了(j)个(111...1),得到的数(mod p =k)的方案.注意选出来的(111...1)不同当且仅当对应的(a)序列排序后不同,并且只有模(p)相同的(111...1)才有可能有影响.转移枚举当前这个类选了多少个j,然后转移系数就是(cnt_i)种数中选(j)个的方案,这个就等于(inom{j+cnt_i-1}{j}),最后答案为(f_{p-1,8,p-(underbrace {111...1}_{n个1}mod p)}),因为没有前导0,要至少包含一个(underbrace {111...1}_{n个1})
#include<bits/stdc++.h>
#define LL long long
#define uLL unsigned long long
#define db double
using namespace std;
const int N=500+10,mod=999911659;
LL rd()
{
LL x=0,w=1;char ch=0;
while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
void ad(int &x,int y){x+=y,x-=x>=mod?mod:0;}
LL n,mi[N],a[N];
int p,sz,f[2][9][N],g[9],inv[9];
bool cr[N];
int C(LL a,int b)
{
a%=mod;
int an=1;
for(int i=1;i<=b;++i,--a)
an=1ll*an*a%mod*inv[i]%mod;
return an;
}
int main()
{
n=rd(),p=rd();
inv[0]=inv[1]=1;
for(int i=2;i<=8;++i) inv[i]=(mod-1ll*mod/i*inv[mod%i]%mod)%mod;
memset(mi,0x3f3f3f,sizeof(mi));
mi[0]=0;
for(int i=1%p,j=1;!cr[i];i=(10ll*i+1)%p,++j)
{
if(mi[i]>j) mi[i]=j;
else cr[i]=1,++sz;
}
for(int i=0;i<p;++i)
{
if(cr[i]) a[i]=max(0ll,(n-mi[i]+sz)/sz);
else a[i]=n>=mi[i];
}
int nw=1,la=0;
f[la][0][0]=1;
g[0]=1;
for(int i=0;i<p;++i)
{
if(!a[i]) continue;
for(int j=1;j<=8;++j) g[j]=C(j+a[i]-1,j);
for(int j=0;j<=8;++j)
for(int k=0;k<p;++k)
{
if(!f[la][j][k]) continue;
for(int l=0;j+l<=8;++l)
ad(f[nw][j+l][(k+l*i)%p],1ll*f[la][j][k]*g[l]%mod);
f[la][j][k]=0;
}
nw^=1,la^=1;
}
int kk=-1;
for(int i=0;i<p;++i)
if(n==mi[i]||(cr[i]&&(n-mi[i])%sz==0)){kk=(p-i)%p;break;}
printf("%d
",f[la][8][kk]);
return 0;
}