题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=2552
看到数据范围,直接就想打表,先写了发dfs暴搜,结果发现连 $5$ $5$ 的点都跑到天荒地老,然后就开始dp。
dp数组一共n维,第i维表示第i行放了几个数。
如果数据范围小一点的话,就可以开一个多维的dp数组,然后大力dp了,但是这个题的数据范围显然是不允许我们这么做的,所以再大胆一点,把9个map套在一起,然后里面再套一个高精度。
代码虽然很暴力,但是打表速度还是很快的。
打表程序:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 |
#include<bits/stdc++.h> #define bit bitset<110> #define ll long long using namespace std; inline int rd(){ int x=0,y=1;char c=getchar(); while(!isdigit(c)){if(c=='-')y=-y;c=getchar();} while(isdigit(c))x=x*10+c-'0',c=getchar(); return x*y; } struct bn{ #define MAXN 1010 #define ll long long int len; char num[MAXN]; bn(ll x){ memset(num,0,sizeof(num)); len=0; while(x>0){ num[len++]=x%10; x/=10; } } bn(){memset(num,0,sizeof(num)),len=0;} void rd(){ len=0; char c=getchar(); while(!isdigit(c))c=getchar(); while(isdigit(c))num[len++]=c-'0',c=getchar(); for(int i=0; i<len/2; i++)swap(num[i],num[len-i-1]); } void out(){ if(!len)printf("0"); for(int i=len-1; i>=0; i--)printf("%d",num[i]); } void half(){ for(int i=len-1; i>0; i--){ num[i-1]+=(num[i]%2)*10; num[i]/=2; } num[0]/=2; while(len-1>=0 && !num[len-1])len--; } friend bn operator + (bn a,bn b){ bn c; for(int i=0; i<a.len || i<b.len; i++){ c.num[i]+=a.num[i]+b.num[i]; c.num[i+1]+=c.num[i]/10; c.num[i]%=10; } c.len=max(a.len,b.len); if(c.num[c.len])c.len++; return c; } friend bn operator + (bn a,ll b){return a+bn(b);} friend bn operator + (ll a,bn b){return bn(a)+b;} friend bn operator - (bn a,bn b){ bn c; for(int i=0; i<a.len; i++){ c.num[i]+=a.num[i]-b.num[i]; if(c.num[i]<0)c.num[i+1]--,c.num[i]+=10; } c.len=max(a.len,b.len); while(c.len-1>=0 && !c.num[c.len-1])c.len--; return c; } friend bn operator - (bn a,ll b){return a-bn(b);} friend bn operator * (bn a,bn b){ bn c; for(int i=0; i<a.len; i++){ for(int j=0; j<b.len; j++){ c.num[i+j]+=a.num[i]*b.num[j]; c.num[i+j+1]+=c.num[i+j]/10; c.num[i+j]%=10; } } c.len=a.len+b.len; while(c.len-1>=0 && !c.num[c.len-1])c.len--; return c; } friend bn operator * (bn a,ll b){return a*bn(b);} friend bn operator * (ll a,bn b){return bn(a)*b;} friend bool operator < (bn a,bn b){ if(a.len!=b.len)return a.len<b.len; for(int i=a.len-1; i>=0; i--)if(a.num[i]!=b.num[i])return a.num[i]<b.num[i]; return false; } friend bool operator == (bn a,bn b){ if(a.len!=b.len)return false; for(int i=0; i<a.len; i++)if(a.num[i]!=b.num[i])return false; return true; } friend bool operator <= (bn a,bn b){ return a<b || a==b; } friend bn operator / (bn a,bn b){ bn c; bn l,r,mid; l=bn(0),r=a; while(l<=r){ mid=l+r; mid.half(); if(mid*b<=a)c=mid,l=mid+1; else r=mid-1; } return c; } friend bn operator % (bn a,bn b){ return a-(b*(a/b)); } friend bn operator ^ (bn x,ll y){ bn z=1; while(y){ if(y&1)z=z*x; x=x*x; y/=2; } return z; } #undef ll #undef MAXN }; int n,m,ans; int Max[11],a[11]; map<int,map<int,map<int,map<int,map<int,map<int,map<int,map<int,map<int,bn> > > > > > > > >f; inline void init(int i,int j){ f.clear(); n=i,m=j; memset(Max,0,sizeof Max); for(int i=1; i<=n; i++)Max[i]=m; } void dfs(int deep,int num){ if(deep==10){ for(int i=1; i<=9; i++){ if(a[i]){ f[a[1]][a[2]][a[3]][a[4]][a[5]][a[6]][a[7]][a[8]][a[9]]=f[a[1]][a[2]][a[3]][a[4]][a[5]][a[6]][a[7]][a[8]][a[9]]+f[a[1]-(i==1)][a[2]-(i==2)][a[3]-(i==3)][a[4]-(i==4)][a[5]-(i==5)][a[6]-(i==6)][a[7]-(i==7)][a[8]-(i==8)][a[9]-(i==9)]; } } return; } for(int i=0; i<=min(Max[deep],num); i++){ a[deep]=i; dfs(deep+1,i); } } inline void work(){ f[0][0][0][0][0][0][0][0][0]=1; dfs(1,m); printf("ans[%d][%d]=\"",n,m); f[Max[1]][Max[2]][Max[3]][Max[4]][Max[5]][Max[6]][Max[7]][Max[8]][Max[9]].out(); cout<<"\";"<<endl; } int main(){ for(int i=1; i<=9; i++){ for(int j=1; j<=9; j++){ init(i,j); if(n==0 && m==0)break; work(); } } return 0; } |
AC程序:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 |
#include<bits/stdc++.h> using namespace std; inline int rd(){ int x=0,y=1;char c=getchar(); while(!isdigit(c)){if(c=='-')y=-y;c=getchar();} while(isdigit(c))x=x*10+c-'0',c=getchar(); return x*y; } int n,m; string ans[10][10]; inline void init(){ ans[1][1]="1"; ans[1][2]="1"; ans[1][3]="1"; ans[1][4]="1"; ans[1][5]="1"; ans[1][6]="1"; ans[1][7]="1"; ans[1][8]="1"; ans[1][9]="1"; ans[2][1]="1"; ans[2][2]="2"; ans[2][3]="5"; ans[2][4]="14"; ans[2][5]="42"; ans[2][6]="132"; ans[2][7]="429"; ans[2][8]="1430"; ans[2][9]="4862"; ans[3][1]="1"; ans[3][2]="5"; ans[3][3]="42"; ans[3][4]="462"; ans[3][5]="6006"; ans[3][6]="87516"; ans[3][7]="1385670"; ans[3][8]="23371634"; ans[3][9]="414315330"; ans[4][1]="1"; ans[4][2]="14"; ans[4][3]="462"; ans[4][4]="24024"; ans[4][5]="1662804"; ans[4][6]="140229804"; ans[4][7]="13672405890"; ans[4][8]="1489877926680"; ans[4][9]="177295473274920"; ans[5][1]="1"; ans[5][2]="42"; ans[5][3]="6006"; ans[5][4]="1662804"; ans[5][5]="701149020"; ans[5][6]="396499770810"; ans[5][7]="278607172289160"; ans[5][8]="231471904322784840"; ans[5][9]="219738059326729823880"; ans[6][1]="1"; ans[6][2]="132"; ans[6][3]="87516"; ans[6][4]="140229804"; ans[6][5]="396499770810"; ans[6][6]="1671643033734960"; ans[6][7]="9490348077234178440"; ans[6][8]="67867669180627125604080"; ans[6][9]="583692803893929928888544400"; ans[7][1]="1"; ans[7][2]="429"; ans[7][3]="1385670"; ans[7][4]="13672405890"; ans[7][5]="278607172289160"; ans[7][6]="9490348077234178440"; ans[7][7]="475073684264389879228560"; ans[7][8]="32103104214166146088869942000"; ans[7][9]="2760171874087743799855959353857200"; ans[8][1]="1"; ans[8][2]="1430"; ans[8][3]="23371634"; ans[8][4]="1489877926680"; ans[8][5]="231471904322784840"; ans[8][6]="67867669180627125604080"; ans[8][7]="32103104214166146088869942000"; ans[8][8]="22081374992701950398847674830857600"; ans[8][9]="20535535214275361308250745082811167425600"; ans[9][1]="1"; ans[9][2]="4862"; ans[9][3]="414315330"; ans[9][4]="177295473274920"; ans[9][5]="219738059326729823880"; ans[9][6]="583692803893929928888544400"; ans[9][7]="2760171874087743799855959353857200"; ans[9][8]="20535535214275361308250745082811167425600"; ans[9][9]="220381378415074546123953914908618547085974856000"; } int main(){ init(); while(1){ int x=rd(),y=rd(); if(x==0 && y==0)break; printf("%s\n",ans[x][y].c_str()); } return 0; } |