欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-06-12 19:28:05
...

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

题目

Time and Memory Limits

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

Description

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

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)都满足xyx≥y的情况下,从(0,0)(0,0)走到(n,m)(n,m)有多少种走法

分析

注意到n,mn,m都是5000的,而且空间很小
普通的nmn*m暴力DPDP不可以
发现有个要求
找规律发现
Ans=Cn+mmCn+mm1Ans=C_{n+m}^m-C_{n+m}^{m-1}
那么高精度安排即可
但是又要打减、乘、除,十分麻烦
尝试化简
a=n+ma=n+m,b=mb=m
Ans=Cn+mmCn+mm1=Cabcab1=a!b!(ab)!a!(b1)!(ab+1)!=a!(ab+1)b!(ab+1)!a!bb!(ab+1)!=a!(a2b+1)b!(ab+1)!=(n+m)!(nm+1)m!(n+1)!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;
}