【BZOJ4005】[JLOI2015] 骗我呢(容斥,组合计数)
题面
BZOJ
洛谷
题解
lalaxu
#include<iostream>
using namespace std;
#define MOD 1000000007
#define MAX 3000300
void add(int &x,int y){x+=y;if(x>=MOD)x-=MOD;}
int n,m,inv[MAX],jc[MAX],jv[MAX],N,ans;
int Calc(int x,int y){if(x<0||y<0)return 0;return 1ll*jc[x+y]*jv[x]%MOD*jv[y]%MOD;}
void flip1(int &x,int &y){swap(x,y);x-=1;y+=1;}
void flip2(int &x,int &y){swap(x,y);x+=m+2;y-=m+2;}
int main()
{
cin>>n>>m;inv[0]=inv[1]=jc[0]=jv[0]=1;N=max(n,m)*3+1;
for(int i=2;i<=N;++i)inv[i]=1ll*inv[MOD%i]*(MOD-MOD/i)%MOD;
for(int i=1;i<=N;++i)jc[i]=1ll*jc[i-1]*i%MOD;
for(int i=1;i<=N;++i)jv[i]=1ll*jv[i-1]*inv[i]%MOD;
int x=n+m+1,y=n;ans=Calc(x,y);
while(x>=0&&y>=0)flip1(x,y),add(ans,MOD-Calc(x,y)),flip2(x,y),add(ans,Calc(x,y));
x=n+m+1,y=n;
while(x>=0&&y>=0)flip2(x,y),add(ans,MOD-Calc(x,y)),flip1(x,y),add(ans,Calc(x,y));
cout<<ans<<endl;
return 0;
}