cf401d
求n的数字重排且整除m的数（无前导0）
这道题我的写法挺鬼畜（用了一直想写却从未成功的11维动态数组）
dp[x][st][……]表示前x位，原数位st，每种数字的个数为……的数。
这里注意一下，0-9一共10个数字，但是只要9维状态就行，因为剩下的可以用x和其他数表示，所以也是确定的，不用写进状态了。
（常数级别的优化，但是这里不优化空间会被卡常）。
下附鬼畜代码TT:
1 #include<bits/stdc .h> 2 #define ll long long 3 using namespace std; 4 int c[10]; 5 ll n,m; 6 int len; 7 ll ***********dp; 8 ll dfs(int x,int st,int fz,int c0,int c1,int c2,int c3,int c4,int c5,int c6, int c7,int c8){ 9 if (x==-1){10 return (st==0);11 }12 if (!fz && dp[x][st][c0][c1][c2][c3][c4][c5][c6][c7][c8]!=-1) return dp[x][st][c0][c1][c2][c3][c4][c5][c6][c7][c8];13 int maxn=9;14 ll ret=0;15 for (int i=0; i<=maxn; i ){16 if (fz){17 switch (i){18 case 1:{if (c1>0) ret =dfs(x-1,(st*10 i)%m,0,c0,c1-1,c2,c3,c4,c5,c6,c7,c8); break;}19 case 2:{if (c2>0) ret =dfs(x-1,(st*10 i)%m,0,c0,c1,c2-1,c3,c4,c5,c6,c7,c8); break;}20 case 3:{if (c3>0) ret =dfs(x-1,(st*10 i)%m,0,c0,c1,c2,c3-1,c4,c5,c6,c7,c8); break;}21 case 4:{if (c4>0) ret =dfs(x-1,(st*10 i)%m,0,c0,c1,c2,c3,c4-1,c5,c6,c7,c8); break;}22 case 5:{if (c5>0) ret =dfs(x-1,(st*10 i)%m,0,c0,c1,c2,c3,c4,c5-1,c6,c7,c8); break;}23 case 6:{if (c6>0) ret =dfs(x-1,(st*10 i)%m,0,c0,c1,c2,c3,c4,c5,c6-1,c7,c8); break;}24 case 7:{if (c7>0) ret =dfs(x-1,(st*10 i)%m,0,c0,c1,c2,c3,c4,c5,c6,c7-1,c8); break;}25 case 8:{if (c8>0) ret =dfs(x-1,(st*10 i)%m,0,c0,c1,c2,c3,c4,c5,c6,c7,c8-1); break;}26 case 9:{if ((x 1-c0-c1-c2-c3-c4-c5-c6-c7-c8)>0) ret =dfs(x-1,(st*10 i)%m,0,c0,c1,c2,c3,c4,c5,c6,c7,c8); break;}27 }28 }29 else {30 switch (i){31 case 0:{if (c0>0) ret =dfs(x-1,(st*10 i)%m,0,c0-1,c1,c2,c3,c4,c5,c6,c7,c8); break;}32 case 1:{if (c1>0) ret =dfs(x-1,(st*10 i)%m,0,c0,c1-1,c2,c3,c4,c5,c6,c7,c8); break;}33 case 2:{if (c2>0) ret =dfs(x-1,(st*10 i)%m,0,c0,c1,c2-1,c3,c4,c5,c6,c7,c8); break;}34 case 3:{if (c3>0) ret =dfs(x-1,(st*10 i)%m,0,c0,c1,c2,c3-1,c4,c5,c6,c7,c8); break;}35 case 4:{if (c4>0) ret =dfs(x-1,(st*10 i)%m,0,c0,c1,c2,c3,c4-1,c5,c6,c7,c8); break;}36 case 5:{if (c5>0) ret =dfs(x-1,(st*10 i)%m,0,c0,c1,c2,c3,c4,c5-1,c6,c7,c8); break;}37 case 6:{if (c6>0) ret =dfs(x-1,(st*10 i)%m,0,c0,c1,c2,c3,c4,c5,c6-1,c7,c8); break;}38 case 7:{if (c7>0) ret =dfs(x-1,(st*10 i)%m,0,c0,c1,c2,c3,c4,c5,c6,c7-1,c8); break;}39 case 8:{if (c8>0) ret =dfs(x-1,(st*10 i)%m,0,c0,c1,c2,c3,c4,c5,c6,c7,c8-1); break;}40 case 9:{if ((x 1-c0-c1-c2-c3-c4-c5-c6-c7-c8)>0) ret =dfs(x-1,(st*10 i)%m,0,c0,c1,c2,c3,c4,c5,c6,c7,c8); break;}41 }42 }43 }44 return dp[x][st][c0][c1][c2][c3][c4][c5][c6][c7][c8]=ret;45 }46 int main(){47 scanf("%lld%lld",&n,&m);48 len=0;49 while (n){50 c[n] ;51 n/=10;52 len ;53 }54 dp=new ll **********[len];55 for (int i=0; i<len; i ){56 dp[i]=new ll*********[m];57 for (int i0=0; i0<m; i0 ){58 dp[i][i0]=new ll********[c[0] 1];59 for (int i1=0; i1<c[0] 1; i1 ){60 dp[i][i0][i1]=new ll*******[c[1] 1];61 for (int i2=0; i2<c[1] 1; i2 ){62 dp[i][i0][i1][i2]=new ll******[c[2] 1];63 for (int i3=0; i3<c[2] 1; i3 ){64 dp[i][i0][i1][i2][i3]=new ll*****[c[3] 1];65 for (int i4=0; i4<c[3] 1; i4 ){66 dp[i][i0][i1][i2][i3][i4]=new ll ****[c[4] 1];67 for (int i5=0; i5<c[4] 1; i5 ){68 dp[i][i0][i1][i2][i3][i4][i5]=new ll ***[c[5] 1];69 for (int i6=0; i6<c[5] 1; i6 ){70 dp[i][i0][i1][i2][i3][i4][i5][i6]=new ll **[c[6] 1];71 for (int i7=0; i7<c[6] 1; i7 ){72 dp[i][i0][i1][i2][i3][i4][i5][i6][i7]=new ll *[c[7] 1];73 for (int i8=0; i8<c[7] 1; i8 ){74 dp[i][i0][i1][i2][i3][i4][i5][i6][i7][i8]=new ll [c[8] 1];75 for (int i9=0; i9<c[8] 1; i9 ){76 dp[i][i0][i1][i2][i3][i4][i5][i6][i7][i8][i9]=-1;77 }78 }79 }80 }81 }82 }83 }84 }85 }86 }87 }88 ll res=dfs(len-1,0,1,c[0],c[1],c[2],c[3],c[4],c[5],c[6],c[7],c[8]);89 printf("%lld",res);90 }
View Code
赞 (0)