【GDOI2014模拟】JZOJ2020年8月14日T2 网格
题目
Time and Memory Limits
Description
某城市的街道呈网格状，左下角坐标为A(0, 0)，右上角坐标为B(n, m)，其中n >= m。现在从A(0, 0)点出发，只能沿着街道向正右方或者正上方行走，且不能经过图示中直线左上方的点，即任何途径的点(x, y)都要满足x >= y，请问在这些前提下，到达B(n, m)有多少种走法。
Input
输入文件中仅有一行，包含两个整数n和m，表示城市街区的规模。
Output
输出文件中仅有一个整数和一个换行/回车符，表示不同的方案总数。
Sample Input
输入1：
6 6
输入2：
5 3
Sample Output
输出1：
132
输出2：
28
Data Constraint
50%的数据中，n = m，在另外的50%数据中，有30%的数据：1 <= m < n <= 100
100%的数据中，1 <= m <= n <= 5 000
题解
题意
给出一个笛卡尔坐标系
问在满足任何途径的点\((x,y)\)都满足\(x≥y\)的情况下，从\((0,0)\)走到\((n,m)\)有多少种走法
分析
注意到\(n,m\)都是5000的，而且空间很小
普通的\(n*m\)暴力\(DP\)不可以
发现有个要求
找规律发现
\[Ans=C_{n+m}^m-C_{n+m}^{m-1}
\]
\]
那么高精度安排即可
但是又要打减、乘、除，十分麻烦
尝试化简
设\(a=n+m\),\(b=m\)
\[Ans=C_{n+m}^m-C_{n+m}^{m-1}\\=C_a^b-c_a^{b-1}\\=\dfrac{a!}{b!(a-b)!}-\dfrac{a!}{(b-1)!(a-b+1)!}\\=\dfrac{a!(a-b+1)}{b!(a-b+1)!}-\dfrac{a!b}{b!(a-b+1)!}\\=\dfrac{a!(a-2b+1)}{b!(a-b+1)!}\\=\dfrac{(n+m)!(n-m+1)}{m!(n+1)!}
\]
\]
那么就可以质因数分解然后相乘即可
Code
#include<bits/stdc++.h>
#define rg register
using namespace std;
long long n,m,x,tot[100005],ans[1000005];
bool b[100005];
inline long long read()
{
long long res=0;char ch;
ch=getchar();
while (ch<'0'||ch>'9') ch=getchar();
while (ch>='0'&&ch<='9')
{
res=(res<<1)+(res<<3)+(ch-'0');
ch=getchar();
}
return res;
}
int main()
{
n=read();m=read();
memset(b,true,sizeof(b));
b[1]=false;
for (rg long long i=2;i<=100005;i++)
for (rg long long j=2;j*i<=100005;j++)
b[i*j]=false;
x=n+1-m;
for (rg long long i=2;i*i<=x;i++)
{
if (b[i]==true&&x%i==0)
{
while (x%i==0)
{
tot[i]++;
x/=i;
}
}
}
if (x>1) tot[x]++;
for (rg long long j=2;j<=n+m;j++)
{
long long k=j;
for (rg long long i=2;i*i<=k;i++)
{
if (b[i]==true&&k%i==0)
{
while (k%i==0)
{
tot[i]++;
k/=i;
}
}
}
if (k>1) tot[k]++;
}
for (rg long long j=2;j<=m;j++)
{
long long k=j;
for (rg long long i=2;i*i<=k;i++)
{
if (b[i]==true&&k%i==0)
{
while (k%i==0)
{
tot[i]--;
k/=i;
}
}
}
if (k>1) tot[k]--;
}
for (rg long long j=2;j<=n+1;j++)
{
long long k=j;
for (rg long long i=2;i*i<=k;i++)
{
if (b[i]==true&&k%i==0)
{
while (k%i==0)
{
tot[i]--;
k/=i;
}
}
}
if (k>1) tot[k]--;
}
ans[0]=1;
ans[1]=1;
for (rg long long i=1;i<=100000;i++)
{
if (b[i]==true&&tot[i]>0)
{
for (rg long long j=1;j<=tot[i];j++)
{
for (rg long long k=1;k<=ans[0];k++)
ans[k]*=i;
x=0;
for (rg long long k=1;k<=ans[0];k++)
{
ans[k]+=x;
x=ans[k]/10;
ans[k]%=10;
}
ans[ans[0]+1]=x;
while (ans[ans[0]+1])
{
ans[0]++;
ans[ans[0]+1]=ans[ans[0]]/10;
ans[ans[0]]%=10;
}
}
}
}
for (rg long long i=ans[0];i>=1;i--)
printf("%lld",ans[i]);
return 0;
}