【GDOI2014模拟】网格

题目

某城市的街道呈网格状，左下角坐标为A(0, 0)，右上角坐标为B(n, m)，其中n >= m。现在从A(0, 0)点出发，只能沿着街道向正右方或者正上方行走，且不能经过图示中直线左上方的点，即任何途径的点(x, y)都要满足x >= y，请问在这些前提下，到达B(n, m)有多少种走法。

分析

首先，我们知道：如果现在从(0, 0)点出发，只能沿着街道向正右方或者正上方行走时，到（n,m）点(n>=m)的方案数是\(C^{m}_{n+m}\)。

发现，任何途径的点(x, y)都要满足x>=y就是不经过粉色线x=y+1

有一条违法的路径：

我们把路径按照粉色线做个对称，

我们发现，到橙色点的路径都一一对应每一条违法路径，也就是说，违法路径的方案数就是到橙色点的方案数。

所以，合法方案数=随便走的方案数-违法方案数=\(C^{m}_{n+m}-C^{m-1}_{n+m}\)

注意：如果直接算可能会超时，要把式子简化，而且高精度要压位。

#include <cmath>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
const int maxlongint=2147483647;
const int mo=10000;
using namespace std;
int f[20000],n,m,g[20000];
inline int times(int x)
{
memcpy(g,f,sizeof(g));
f[1]=0;
f[0]=g[0]+4;
for(int i=1;i<=f[0];i++)
{
f[i]+=g[i]*x;
f[i+1]=f[i]/mo;
f[i]-=f[i+1]*mo;
}
while(!f[f[0]] && f[0]>1)
f[0]--;
}
inline int div(int x)
{
memcpy(g,f,sizeof(g));
int k=0;
for(int i=g[0];i>=1;i--)
{
f[i]=(k*mo+g[i])/x;
k=(k*mo+g[i])-x*f[i];
}
f[0]=g[0];
while(!f[f[0]] && f[0]>1)
f[0]--;
}
int main()
{
scanf("%d%d",&n,&m);
f[0]=1;
f[1]=1;
int j=2;
for(int i=n+2;i<=n+m;i++)
{
if(j<=m)
{
if(i%j==0)
{
times(i/j);
j++;
}
else
times(i);
}}
times(n+1-m);
for(int i=j;i<=m;i++)
{
div(i);
}
for(int i=f[0];i>=1;i--)
{
if(f[0]!=i)
printf("%04d",f[i]);
else
printf("%d",f[i]);
}
}