【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;

}

巴特西

【GDOI2014模拟】JZOJ2020年8月14日T2 网格

【GDOI2014模拟】JZOJ2020年8月14日T2 网格

题目

Time and Memory Limits

Description

Input

Output

Sample Input

Sample Output

Data Constraint

题解

题意

分析

Code

最新文章

热门文章