[JLOI2015]骗我呢

Posted by Dispwnl on April 18, 2019

题目

题解

yyb

代码

# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
using namespace std;
const int MAX=4e6+5,mod=1e9+7;
int n,m;
int fac[MAX],inv[MAX],Inv[MAX];
void rev(int &x,int &y) {--y,++x,swap(x,y);}
void ver(int &x,int &y) {y+=(m+2),x-=(m+2),swap(x,y);}
int C(int n,int m) {return 1ll*fac[n+m]*Inv[m]%mod*Inv[n]%mod;}
int main()
{
	scanf("%d%d",&n,&m),fac[0]=fac[1]=inv[0]=inv[1]=Inv[0]=Inv[1]=1;
	for(int i=2;i<=2*(n+m+1);++i)
	  fac[i]=1ll*fac[i-1]*i%mod,inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod,Inv[i]=1ll*Inv[i-1]*inv[i]%mod;
	int x=n+m+1,y=n,ans=C(x,y);
	while(x>=0&&y>=0) rev(x,y),(x>=0&&y>=0?(ans+=mod-C(x,y))%=mod:0),ver(x,y),(x>=0&&y>=0?(ans+=C(x,y))%=mod:0);
	x=n+m+1,y=n;
	while(x>=0&&y>=0) ver(x,y),(x>=0&&y>=0?(ans+=mod-C(x,y))%=mod:0),rev(x,y),(x>=0&&y>=0?(ans+=C(x,y))%=mod:0);
	return printf("%d",ans),0;
}