因为整个矩阵是m×n的，那么从左上角走到右下角就必定需要向右走 m步，向下走n步，所以总共要走的步数就是m+n步。那么其实总的方案数就是在总的步数m+n中，找出向右走m步的组合或者是向下走n步的组合即可。因此本体的答案即为C(m,m+n)或者是(n,m+n)。那么先把组合数的代码写出来： //ll即为long long inline ll C(ll p,ll q)//C(p,q)=q!/(p!(q-p)!) { ll res=1; if (p==0) return res; for (register int i=p+1;i<=q;++i) res=res*i/(i-n); return res; } 从代码可以看出，计算C(p,q)要从p+1循环到q。在这里，q即为m+n，p可为m或n。显然，当p取n时，复杂度小得多（因为m是一个小于4的数）因此，这个题目就变为了给出m和n，求出C(n,m+n)的题目了。但这个时候你交上去还会是60分，因为m和n都取最大值时，答案有30位，因此还得写个高精度啊（高精乘低精&高精除低精）。最后，该题还有一个坑，就是答案只要保留前17位，之后的全输出0（害我调了好久qwq）之后便可以愉快的AC了。 code: ```cpp #include #include #include #include using namespace std; #define ll long long inline ll read(); struct big_num { int a[1010]; int len; inline void big_num_memset() { memset(a,0,sizeof(a)); a[1]=1; len=1; } }; big_num operator * (const big_num &a,const int b) { int L=a.len,jw=0; big_num c=a; for (register int i=1;i<=L;++i) { c.a[i]=c.a[i]*b+jw; jw=c.a[i]/10; c.a[i]%=10; } ++L; c.a[L]=jw; while (c.a[L]!=0) c.a[L+1]+=c.a[L]/10,c.a[L]%=10,++L; --L; c.len=L; return c; } big_num operator / (const big_num &a,const int b) { big_num c=a; int tw=0,L=a.len; for (register int i=L;i>=1;--i) { int k=(tw*10+c.a[i])/b; tw=(tw*10+c.a[i])%b; c.a[i]=k; } while (c.a[L]==0) --L; c.len=L; return c; } inline big_num C(ll n,ll m)//C(n,m)=m!/(n!(m-n)!) { big_num res; res.big_num_memset(); if (n==0) return res; for (register int i=n+1;i<=m;++i) res=res*i/(i-n); return res; } inline void print(big_num a) { if (a.len>17) { for (register int i=a.len;i>=a.len-16;--i) cout<=1;--i) cout<<"0"; } else for (register int i=a.len;i>=1;--i) cout<

A20968.矩阵 III

题目描述

输入格式

输出格式

输入输出样例

说明/提示