玄学问题???
查看原帖
玄学问题???
378346
expnoi楼主2023/7/6 21:08
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
	int s=0,w=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-')w=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')s=(s<<3)+(s<<1)+(c^48),c=getchar();
	return s*w;
}
inline void print(int x)
{
	if(x<0)x=-x,putchar('-');
	if(x>=10)print(x/10);
	putchar(x%10+48);
}
const int mod=1e9+7;
int n,m,fac[3000010],Inv[3000010];
inline void exgcd(int a,int b,int &x,int &y)
{
	if(!b)
	{
		x=1,y=0;
		return;
	}
	exgcd(b,a%b,x,y);
	int tmp=x;
	x=y;
	y=tmp-(a/b)*y;
}
inline int inv(int a)
{
	int x=0,y=0;
	exgcd(a,mod,x,y);
	x%=mod;
	x+=mod;
	x%=mod;
	return x;
}
inline void mirror1(int &x,int &y)
{
	swap(x,y);
	x--;
	y++;
}
inline void mirror2(int &x,int &y)
{
	swap(x,y);
	x+=m+2;
	y-=m+2;
}
inline int C(int n,int m)
{
	return fac[n]*Inv[m]%mod*Inv[n-m]%mod;
}
signed main()
{
	n=read();
	m=read();
	fac[0]=1;
	for(int i=1;i<=3000001;i++)fac[i]=fac[i-1]*i%mod;
	Inv[3000001]=inv(fac[3000001]);
	for(int i=3000000;i>=0;i--)Inv[i]=Inv[i+1]*(i+1)%mod;
	int x=n+m+1,y=n,ans=C(x+y,x);//可以考虑画一个平行四边形想象一下。
	while(x>=0&&y>=0)//以A开始的不符合的所有方案容斥 
	{
		mirror1(x,y);
		if(y>=0&&x>=0)
		{
			ans-=C(x+y,x);
			ans%=mod;
			ans+=mod;
			ans%=mod;
		}
		mirror2(x,y);//再对称,在A后多出一个B
		if(y>=0&&x>=0)
		{
			ans+=C(x+y,x);
			ans%=mod;
			ans+=mod;
			ans%=mod;
		}
	}
	x=n+m+1,y=n;
	while(x>=0&&y>=0)
	{
		mirror2(x,y);
		if(y>=0&&x>=0)
		{
			ans-=C(x+y,x);
			ans%=mod;
			ans+=mod;
			ans%=mod;
		}
		mirror1(x,y);
		if(y>=0&&x>=0)
		{
			ans+=C(x+y,x);
			ans%=mod;
			ans+=mod;
			ans%=mod;
		}
	}
	print(ans);
}

我把mirror两个函数(没有返回值)的类型改成了void就过了,但是我不理解为什么原来过不了。求大佬指点/kel

2023/7/6 21:08
加载中...