[bzoj1974][51nod1261][DP]auction 代码拍卖会上升数_综合

Description

一个10进制表示的正整数，如果从左到右，每一位的数字都不小于前一位的数字，则被称为上升数。例如：1234, 111, 58,
8899是上升数，而314, 7654, 2009不是。
给出长度N和一个数K，求有多少个长度恰好为N的上升数，是K的倍数。由于数量很大，输出Mod 1000000007的结果。例如：N =
2，K = 12，符合条件的数有4个，分别是：12, 24, 36, 48。
Input
一行：两个数N（1≤N≤10^18）、P(1≤P≤500)，用一个空格分开。

Output

一行：一个数，表示答案除以999911659的余数。
51nod：mod 1e9+7

Sample Input

2 3

Sample Output

15

HINT

样例解释

方案可以是：12 15 18 24 27 33 36 39 45 48 57 66 69 78 99，共15种。

数据规模

测试点 N P 测试点 N P

1 ≤1000 ≤500 6 ≤10^6 ≤500

2 ≤10^18 5 7 ≤10^18 ≤120

3 ≤10^18 ≤10 8 ≤10^18 ≤500

4 ≤10^18 ≤10 9 ≤10^18 ≤500

5 ≤10^18 25 10 ≤10^18 ≤500

题解

老年选手只想得到 $O(k^2*9^3*logn)$ 的_TLE做法辣…
还是用到了那个套路
112233344
111111111
–11111111
…
显然最多只会有9种不同的111…11
发现模数很小，本质不同的111…111只会有模数种
预处理这些种类的111…111数量
做背包dp
$f [i] [j] [k]$ 表示前i组选了j个mod=k
一组中选出k个允许重复的方案数是 $C_{sum+k-1}^{k}$
~~老年跑的这么慢啊…~~

模数1e9+7版…

#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<queue> #include<vector> #include<ctime> #include<map> #define LL long long #define mp(x,y) make_pair(x,y) using namespace std; inline LL read() {
     LL f=1,x=0;char ch=getchar();while(ch<'0'||ch>'9'){
     if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
     x=x*10+ch-'0';ch=getchar();}return x*f; } inline void write(int x) {
     if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10+'0'); } inline void print(int x){
     write(x);printf(" ");} const LL md=1e9+7; int mod;LL n,f[2][9][505],inv[505];//第i组 总共选出j个值 mod=K  void ad(LL &x,LL y){
     x+=y;if(x>=md)x-=md;} int v[505]; LL pow_mod(LL a,LL b) {
     LL ret=1;while(b){
     if(b&1)ret=ret*a%md;a=a*a%md;b>>=1;}return ret; } LL pow_mod_1(LL a,LL b) {
     LL ret=1;while(b){
     if(b&1)ret=ret*a%mod;a=a*a%mod;b>>=1;}return ret; } LL C(LL n,LL m) {
     LL ret=1;for(LL i=n;i>=n-m+1;i--)ret=ret*(i%md)%md;ret=ret*inv[m]%md;return ret; } LL calc(LL len) {
     if(len==1)return 1;LL mid=len>>1;LL u=calc(mid);u=(u*pow_mod_1(10,mid)%mod+u)%mod;if(len&1)u=(u*10+1)%mod;return u; } int fac[505]; int main() {
     LL s=1;inv[1]=inv[0]=1;for(int i=2;i<=500;i++)s=s*i%md,inv[i]=pow_mod(s,md-2);memset(v,-1,sizeof(v));n=read();mod=read();LL tmp=0;LL p1=n+1,p2=0;for(int i=1;i<=n;i++){
     tmp=(tmp*10+1)%mod;if(v[tmp]!=-1){
     p1=i;p2=v[tmp];break;}v[tmp]=i;fac[i]=tmp;}LL sss;if(p1>n)sss=fac[n];else{
     int ok=(n-p2)%((LL)p1-p2);sss=fac[ok+p2];}int now=0;f[0][0][sss]=1;for(int i=0;i<mod;i++)if(v[i]!=-1){
     now^=1;memset(f[now],0,sizeof(f[now]));LL sum=(n-p2)/(p1-p2);if(v[i]-p2<=(n-p2)%(p1-p2)&&p1<=n&&v[i]>p2)sum++;if(v[i]==p2)sum++;if(v[i]<p2)sum=1;if(p1>n)sum++;for(int l=0;l<mod;l++)for(int j=0;j<=8;j++)for(int k=0;k<=j;k++){
     int gg=i*k%mod;int ok=(l-gg+mod)%mod;ad(f[now][j][l],f[now^1][j-k][ok]*C(sum+k-1,k)%md);}}LL ans=0;for(int i=0;i<=8;i++)ad(ans,f[now][i][0]);printf("%lld\n",ans);return 0; }```