【问题描述】 求n位无前导零且数码从高到低非降并模 m等于 0的数个数。 【输入格式】 两行个整数 n， m； 【输出格式】 一行个整数代表答案模 10^9+7之后的值 。 【样例输入1】 2 12 【样例输出1】 4 【样例输入2】 3 111 【样例输出2】 9 【样例输入3】 452 10 【样例输出3】 0 【样例输入4】 6 58 【样例输出4】 38 【数据规模与约定】 对于 100%的数据， 1≤n≤10^18, 1≤m≤500，有各种部分 。
思路： 神奇的dp，%大佬，get代码，add注释
#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #define LL long long using namespace std; const int M=520, P=1000000007; LL n; int m,lst[M],cnt[M],inv[10],f[9][M],C[M][9],g[M][9],u[9][9]; //考虑ans的性质，非下降，位数又是固定的，所以我们可以把ans分成最多九个形如11111..的数 //eg：12345 = 11111 + 1111 + 111 + 11 + 1； 155579 = 111111 + 11111 + 11111 + 11111 + 11111 + 11 + 11 + 1 + 1; //因为ans的位数固定为n；所以最下面一层一定是n个1这个数。 //那么我们就可以算这类型的数可以组成多少符合条件的数。 int main(){ freopen ("c.in", "r", stdin); freopen ("c.out", "w", stdout); inv[1] = 1; for(int i=2; i<=8; i++)//预处理1~8的逆元 inv[i] = (LL)inv[P%i] * (P-P/i)%P;//递推求法 /*for(int i=1; i<=8; i++) cout << inv[i] << endl;*/ scanf("%I64d%I64d", &n, &m); //n = 15, m = 12; int v=0; for(int i=1; i<=n; i++){ v = (v * 10 + 1) % m;//遍历所有位数在1~n之间，形似1,11,111的数字 if(v==0 || lst[v]){//之前枚举过一个数字 % m = v，也就是说我们找到了循环（v=0说明循环节就是1） int sz=i-lst[v], tv=v;//sz就是循环节的长度 for(int j=0; j<sz; j++){//遍历整个循环节的模数 if((n-i-j) % sz == 0) v = tv;//剩下的数字个数是sz的整数倍，也就是说tv（v）就是最后一个数（n个1）%m的ans cnt[tv] = (cnt[tv] + (n>=i+j ? (n-i-j+sz)/sz : 0)) % P;//在一个循环节内每个模数只会出现一次 //统计之后有几个循环节就可以知道这一堆数中（1个1，2个1...）%m=x的有cnt[x]个 tv = (tv * 10 + 1) % m; } break; } cnt[v]++; lst[v] = i;//i个1 % m = v } for(int i=0; i<m; i++){// int t=1; for(int j=0;j<9;j++){ C[i][j] = t;//C[i][j]表示从这一堆数（1个1，2个1...）中找出j个%m=i的数有多少种方案 t = (LL)t * (cnt[i]-j) % P * inv[j+1] % P;//阶乘式子往下走 //printf("Y %d %d %d\n", i, j, [i][j]); } } u[0][0] = 1;//u[i][j]表示在i层中填充j种数的方案数，注意是填充而不是选j层出来，每个数一定要放进去。 //eg：u[3][2] = 2; 也就是说在3层中填充2种数的方案数为2，假设我们的2种数是1,2 //填充方式是1,1,2或者1,2,2。不计顺序（因为我们最终的ans是它们的和） //u[i][j] = C（i-1， j-1）(组合数) 夹棍法考虑，因为不计顺序，那么我们的任务就是把i层分成j段，每段一个数 //所以u的求法就有两种下面是根据意义的递推，也可以直接算组合数 for(int i=1; i<9; i++) for(int j=1; j<=i; j++){ for(int k=1; k<=i; k++) (u[i][j] += u[i-k][j-1]) %= P;//递推 //在i层中填充j种数的方案数=在i-k层中填充j-1种数的方案数（剩下的层填充最后一种）顺序并没有影响 //printf("Y %d %d %d\n", i, j, [i][j]); } for(int i=0; i<m; i++){ for(int j=0; j<9; j++){ for(int k=0; k<=j; k++) g[i][j] = (g[i][j] + (LL)u[j][k] * C[i][k]) % P; //g[i][j]表示从这一堆数（1个1，2个1...）中找出j个%m=i的数的方案数（一个数可以选择多次） //从这一堆数（1个1，2个1...）中找出个%m=i的数的方案数 有C[i][k] //把这k个数放到这j层中的方案数有u[j][k]种，所以就是这样递推 //printf("Y %d %d %d\n", i, j, g[i][j]); } } f[0][v] = 1;//f[i][j]表示放上i层，使得所得ans%m=j的方案数 for(int i=0; i<m; i++){ for(int j=7; j>=0; j--){//类似背包 for(int k=j+1; k<9; k++){ for(int l=0; l<m; l++){ int &t = f[k][(l+i*(k-j))%m]; t = (t + (LL)f[j][l] * g[i][k-j]) % P;//选择k-j层放上%m=i的数，ans%m就=l+i*(k-j) } } } } int ans = 0; for(int i=0; i<9; i++) (ans += f[i][0]) %= P; printf("%d\n", ans); }