#组合计数，动态规划#JZOJ 1523 洛谷 2481 代码拍卖会

本文主要是介绍#组合计数，动态规划#JZOJ 1523 洛谷 2481 代码拍卖会，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

问多少个$n$位数满足数位从左到右数字不下降且为$P$的倍数

---

分析

慢慢填坑吧

---

代码

#include <cstdio>
#define rr register
using namespace std;
typedef long long ll;
const ll mod=999911659;
ll n,p,rep,cnt[501],pos[501],dp[501][501][11],inv[11],c[501][11],reco,len,ans;
signed main(){scanf("%lld%lld",&n,&p); rr ll sum=0;if (n<=p){for (rr int i=1;i<=n;++i) ++cnt[sum=(sum*10+1)%p];rep=sum;}else{for (rr int i=1;i<=p+1;++i){if (cnt[sum=(sum*10+1)%p]){ reco=pos[sum],len=i-pos[sum];break; }++cnt[sum],pos[sum]=i;}for (rr int i=0;i<p;++i)if (cnt[i]&&pos[i]>=reco){cnt[i]=(n-reco+1)/len;if (pos[i]-reco+1<=(n-reco+1)%len) ++cnt[i];if ((pos[i]-reco+1)%len==(n-reco+1)%len) rep=i;}}inv[0]=inv[1]=1;for (rr int i=2;i<9;++i) inv[i]=inv[mod%i]*(mod-mod/i)%mod;for (rr int i=0;i<p;++i){c[i][0]=1;if (cnt[i]) for (rr int j=1;j<9;++j)c[i][j]=cnt[i]*c[i][j-1]%mod*inv[j]%mod,cnt[i]=(cnt[i]+1)%mod;}dp[0][rep][0]=1;for (rr int i=0;i<p;++i)for (rr int j=0;j<p;++j)for (rr int k=0;k<9;++k)for (rr int h=0;h<=k;++h)(dp[i+1][j][k]+=dp[i][((j-(i*h)%p)+p)%p][k-h]*c[i][h]%mod)%=mod;for (rr int i=0;i<9;++i) (ans+=dp[p][0][i])%=mod;return !printf("%lld",ans);
} 

这篇关于#组合计数，动态规划#JZOJ 1523 洛谷 2481 代码拍卖会的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---