时间限制: 1 s空间限制: 64000 KB
题目描述 Description
因为是学生，所以显然小A每天都要上学。小A所在的城市的道路构成了一个n*m的网格，每条道路都是可以单向通行的。小A家在点(1,1)，学校在点(n,m)。在不移出边界的情况下，小A可以从点(x,y)移动到点(x+1,y)或(x,y+1)。为了追求新鲜感，小A经常走不同的道路去上学。有一天，小A突发奇想：到底他可以有多少种不同的上学路线呢？
输入描述 Input Description
两个正整数n,m,意义如前所述。
输出描述 Output Description
一个正整数，小A的上学路线数量。
样例输入 Sample Input
2 3
样例输出 Sample Output
3
数据范围及提示 Data Size & Hint
对于30%的数据，n,m<=100;
对于100%的数据，n+m<=40000.
是不是感覺這道題很水啊（才怪呢，有沒有看數據範圍）。 搜索代碼（10分）： #include<cstdio> int n,m,ans; void dfs(int x,int y){ if(x==n&&y==m){++ans;return;} if(y<m) dfs(x,y+1); if(x<n) dfs(x+1,y); } int main(){ scanf("%d%d",&n,&m); dfs(1,1); printf("%d ",ans); return 0; } 對的，這是個DP題。 數據： 1 1 1 1 1 1 1 1 1 1 1 2 3 4 5 6 7 8 9 10 1 3 6 10 15 21 28 36 45 55 1 4 10 20 35 56 84 120 165 220 1 5 15 35 70 126 210 330 495 715 1 6 21 56 126 252 462 792 1287 2002 1 7 28 84 210 462 924 1716 3003 5005 1 8 36 120 330 792 1716 3432 6435 11440 1 9 45 165 495 1287 3003 6435 12870 24310 1 10 55 220 715 2002 5005 11440 24310 48620 相信聰明的，你，一定，看出了DP方程。 f[i][j]=f[i-1][j]+f[i][j-1]; 不要問我為什麼，DP是玄學。 代碼實現（10）： #include<cstdio> int n,m,f[3000][3000]; int main(){ scanf("%d%d",&n,&m);f[0][1]=1; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) f[i][j]=f[i-1][j]+f[i][j-1]; printf("%d ",f[n][m]); return 0; } 為什麼還是10分，啊啊啊。。。（省略很多） 我們來看看問題， Wa：爆int了。 Re：開的數組不夠大了。 對於Re，因為根據DP方程看，我們只需要一層的數據就夠了。(f[j]+=f[j-1];) 對於Wa，我們只需要使用高精就行了。 還有一個Tle，恩，可能是哪裡卡住了吧。 恩，讓我平靜一下。 代碼實現（不要管這個）：我正寫著寫著，旁邊那個同學突然說，****，這個題是組合數，你看看題解，沒有用DP的。 啊，我的上帝原諒我，我點擊題解，快速瀏覽了一下，好像真的，而且一個大佬還說最高二十萬位的樣子。 。。。 慫它嗎？ 舉（5,5）為例，按f[5][5]=f[4][5]+f[5][4];f[4][5]=f[3][5]+f[4][4],f[5][4]=f[4][4]+f[5][3];f[3][5]=f[2][5]+f[3][4],2*f[4][4]=2*f[4][3]+2*f[3][4];f[5][3]=f[5][2]+f[4][3]...... 即f[5][5]=20*f[2][1]+10*f[3][1]+4*f[4][1]+f[5][1]+20*f[1][2]+10*f[1][3]+4*f[1][4]+1*f[1][5]=20+10+4+1+20+10+4+1; 額，你看出什麼來了嗎？我沒看出來。。。 那麼， 1 1 1 1 1 1 1 1 1 1 1 2 3 4 5 6 7 8 9 10 1 3 6 10 15 21 28 36 45 55 1 4 10 20 35 56 84 120 165 220 1 5 15 35 70 126 210 330 495 715 1 6 21 56 126 252 462 792 1287 2002 1 7 28 84 210 462 924 1716 3003 5005 1 8 36 120 330 792 1716 3432 6435 11440 1 9 45 165 495 1287 3003 6435 12870 24310 1 10 55 220 715 2002 5005 11440 24310 48620 f[2][3]=f[2][1]+f[1][2]+f[1][3]=1+1+1; f[3][3]=f[3][1]+2*f[2][1]+2f[1][2]+f[1][3]=1+2+2+1； f[4][3]=f[4][1]+2*f[3][1]+3*f[2][1]+3*f[1][2]+f[1][3]=1+2+3+3+1; f[5][3]=......
好吧，C(n,m)=m!/n!(m-n)!。
要處理一下n、m。
if(n<m){a=m,m=n,n=a;}
n--;m+=n-1;
也就是組合數加高精。
代碼實現：
1 #include<cstdio> 2 using namespace std; 3 int n,m,a,ans[13000]={1,1},bz[13000]; 4 int s[40000],g[40000]; 5 int v[40000]; 6 void zzs(int x,bool y){ 7 for(int j=1;j<=s[0]&&x!=1;j++) 8 while(x%s[j]==0){ 9 if(y) ++g[j]; 10 else --g[j]; 11 x/=s[j]; 12 } 13 } 14 void gjc(int x){ 15 g[x]--; 16 for(int i=1;i<=ans[0];i++){ 17 ans[i]=ans[i]*s[x]+bz[i];bz[i]=0; 18 if(ans[i]>9){ 19 bz[i+1]=ans[i]/10; 20 ans[i]%=10; 21 if(i==ans[0]) ++ans[0]; 22 } 23 } 24 } 25 int main(){ 26 for(int i=2;i<=40000;i++) 27 if(!v[i]){ 28 a=2*i;s[++s[0]]=i; 29 while(a<=40000){v[a]=1;a+=i;} 30 } 31 scanf("%d%d",&n,&m); 32 if(n<m){a=m,m=n,n=a;} 33 n--;m+=n-1; 34 for(int i=n+1;i<=m;i++) zzs(i,1); 35 for(int i=1;i<=m-n;i++) zzs(i,0); 36 for(int i=1;i<=s[0];i++) 37 while(g[i]) gjc(i); 38 for(int i=ans[0];i>0;i--) printf("%d",ans[i]); 39 printf(" "); 40 return 0; 41 }
最高12039位，呵呵。