链接

　　http://codevs.cn/PRoblem/1515/

题解

　　首先这是一张组合数表，f(i,j)=Cii+j$f(i,j)=C_{i+j}^i$ 　　设m≤n$m/le n$，你会发现最优策略总是从(0,0)$(0,0)$走到(n,0)$(n,0)$，然后再去(n,m)$(n,m)$，上述都是说的走直线。 　　将这张表用组合数的形式写出来，会发现 　　ans=n+C0n+C1n+1+C2n+2+...+Cmn+m=n+Cnn+Cnn+1+Cnn+2+...+Cnn+m=n+Cn+1n+1+Cnn+1+Cnn+2+...+Cnn+m=n+Cn+1n+2+Cnn+2+...Cnn+m=n+Cn+1n+3+Cnn+3+...+Cnn+m=...=n+Cn+1n+m+1=n+Cmn+m+1 $$ans=n+C_n^0+C_{n+1}^1+C_{n+2}^2+...+C_{n+m}^m//=n+C_n^n+C_{n+1}^n+C_{n+2}^n+...+C_{n+m}^n//=n+C_{n+1}^{n+1}+C_{n+1}^n+C_{n+2}^n+...+C_{n+m}^n//=n+C_{n+2}^{n+1}+C_{n+2}^n+...C_{n+m}^n//=n+C_{n+3}^{n+1}+C_{n+3}^n+...+C_{n+m}^n//=...//=n+C_{n+m+1}^{n+1}//=n+C_{n+m+1}^m$$ 　　因此对于这道题目 　　ans=max(n,m)+Cmin(n,m)n+m+1 $$ans=max(n,m)+C_{n+m+1}^{min(n,m)}$$ 　　网上老用什么lacus什么的，但完全没有必要…，题目中有个条件nm≤1012$nm/le 10^{12}$，那么min(n,m)≤106$min(n,m)/le 10^6$，使用高中数学中所说的“组合数的计算式”，是可以O(min(n,m))$O(min(n,m))$求出的。

代码