luck 没什么好说的，就是一道裸题 但需要注意的是时间是O(n*k),1e7级别，这个级别是会卡常的，所以要进行优化
这是90分代码 #include<bits/stdc++.h> using namespace std; typedef long long ll; ll ans=0; int mod=1e9+7; const int N=5e4+5; int y,z; int dp[N][505]; ll dfs(int dep,int state,int p){ int tmp=y-state; if(dp[state][p]!=-1) return dp[state][p]; if(tmp==0){ return dp[state][p]=(p==0); } if(tmp==1){ return dp[state][p]=((p*10%z+1)%z==0); } ll sum=0; int limit=min(tmp,9); for(int x=1;x<=limit;x++){ sum=(dfs(dep+1,state+x,(p*10+x)%z)+sum)%mod; } dp[state][p]=sum; return dp[state][p]; } int main(){ scanf("%d%d",&y,&z); memset(dp,-1,sizeof(dp)); ll ans=dfs(1,0,0); printf("%lld",ans); } 这个代码和上一个的时间差不多 #include<bits/stdc++.h> #define re register using namespace std; typedef long long ll; ll ans=0; int mod=1e9+7; const int N=5e4+10; int y,z; int dp[N][505]; bool vis[N]; int main(){ scanf("%d%d",&y,&z); dp[0][0]=1; for(re int i=1;i<=9;i++)dp[i][i%z]=1; for(re int k=1;k<y;k++) for(re int i=1;i<=9;i++){ if(i+k>y) break; for(re int j=0;j<z;j++){ if(!dp[k][j]) continue; int nxt=k+i,val=(j*10%z+i%z)%z; dp[nxt][val]=(1ll*dp[k][j]+dp[nxt][val])%mod; } } printf("%d",dp[y][0]); } #include<bits/stdc++.h> #define re register using namespace std; typedef long long ll; ll read(){ ll ans=0;char c=getchar(); while(c>'9'||c<'0') c=getchar(); for(;'0'<=c&&c<='9';c=getchar()) ans=(ans<<3)+(ans<<1)+c-'0'; return ans; } int mod=1e9+7; const int N=5e4+10; int y,z; int dp[N][505]; bool vis[N]; int main(){ y=read(),z=read(); dp[0][0]=1; for(re int i=1;i<=9;i++)dp[i][i%z]=1; for(re int k=1;k<y;k++) for(re int i=1;i<=9;i++){ if(i+k>y) break; for(re int j=0;j<z;j++){ if(!dp[k][j]) continue; int nxt=k+i,val=(j*10+i)%z; dp[nxt][val]=(dp[k][j]+dp[nxt][val])%mod; } } printf("%d",dp[y][0]); }总结1ll和%在1e7的时候尤其要注意，可能会被卡掉常数
