从矩阵左下角（0,0）出发，到达右上角（n，m），只能向上走或者向右走，不穿过y=x的方案数，1 <= m <= n <= 5 000。
解
很容易联想到不触碰的方案数，应该为(C_{m+n-1}^m-C_{m+n-1}^n),应为不触碰可以一一对应，而不穿过则不满足这个性质，于是考虑构造出不触碰，其实就是不触碰(y=x+1)的方案数，又考虑到起点不一致，不能一一对应，于是起点左移（-1，0），发现此时正好能与题目原设一一对应，
故有
[C_{n+m}^{n}-C_{n+m}^{n+1}
]
利用公式打阶乘质因数分解高精即可。
参考代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#define il inline
#define ri register
using namespace std;
struct lll{
int num[5000];
il lll(){num[0]=1;}
il void clear(){
memset(num,0,sizeof(num));
num[0]=1;
}
il void read(){
string s;cin>>s;num[0]=s.size();
for(ri int i(1);i<=num[0];++i)
num[i]=s[num[0]-i]-48;
while(!num[num[0]]&&num[0]>1)--num[0];
}
il void operator=(string s){
num[0]=s.size();
for(ri int i(1);i<=num[0];++i)
num[i]=s[num[0]-i]-48;
}
il void operator=(int x){
num[0]&=0;
while(x)num[++num[0]]=x%10,x/=10;
}
il void print(){
for(ri int i(num[0]);i;--i)
putchar(num[i]+48);
}
il lll operator*(lll x){
lll y;y.clear();
for(ri int i(1),j,k;i<=num[0];++i){
k=0;
for(j=1;j<=x.num[0];++j)
y.num[i+j-1]+=num[i]*x.num[j]+k,
k=y.num[i+j-1]/10,y.num[i+j-1]%=10;
y.num[i+x.num[0]]+=k;
}y.num[0]=num[0]+x.num[0];
while(!(y.num[y.num[0]])&&y.num[0]>1)--y.num[0];
return y;
}
il lll operator-(lll x){
lll y(*this);ri int i;
for(i=1;i<=y.num[0];++i){
y.num[i]-=x.num[i];
if(y.num[i]<0)y.num[i]+=10,--y.num[i+1];
}while(!(y.num[y.num[0]])&&y.num[0]>1)--y.num[0];
return y;
}template<class free>
il lll operator^(free y){
lll x(*this),ans;ans=1;
while(y){
if(y&1)ans=ans*x;
x=x*x,y>>=1;
}return ans;
}
}temp[1250];
bool check[10001];
int prime[1250],pt;
il lll C(int,int);
il void sieve(int);
int main(){
int n,m;sieve(10000);
scanf("%d%d",&n,&m);
(C(n+m,n)-C(n+m,n+1)).print(),
putchar('
');
return 0;
}
il void sieve(int n){
int i,j;check[1]|=true;
for(i=2;i<=n;++i){
if(!check[i])prime[++pt]=i,temp[pt]=i;
for(j=1;j<=pt&&i*prime[j]<=n;++j){
check[prime[j]*i]|=true;
if(!(i%prime[j]))break;
}
}
}
il lll C(int n,int r){
if(n<r)return temp[0];
int i,j,tr;lll ans;ans=1;
for(i=1;i<=pt;++i){
tr&=0;
for(j=n;j;j/=prime[i])tr+=j/prime[i];
for(j=r;j;j/=prime[i])tr-=j/prime[i];
for(j=n-r;j;j/=prime[i])tr-=j/prime[i];
ans=ans*(temp[i]^tr);
}return ans;
}