P3266 [JLOI2015]骗我呢

#include <cstdio>
#include <iostream>
using namespace std;
#define pii pair< int , int >
#define fi first
#define sc second
#define mp make_pair 

const int MAXN = 3e6 , Mod = 1e9 + 7;
#define Add( x , y ) ( x + y >= Mod ? x + y - Mod : x + y )
#define Sub( x , y ) ( x - y < 0 ? x + Mod - y : x - y )
#define Mul( x , y ) ( 1ll * x * y % Mod )
int Qkpow( int x , int po ) { int p = 1; for( ; po ; po >>= 1 , x = Mul( x , x ) ) if( po & 1 ) p = Mul( p , x ); return p; }
int Inv( int x ) { return Qkpow( x , Mod - 2 ); }
int fac[ MAXN + 5 ] , ivf[ MAXN + 5 ];
void Init( ) {
	fac[ 0 ] = 1;
	for( int i = 1 ; i <= MAXN ; i ++ ) fac[ i ] = Mul( fac[ i - 1 ] , i );
	ivf[ MAXN ] = Inv( fac[ MAXN ] );
	for( int i = MAXN ; i >= 1 ; i -- ) ivf[ i - 1 ] = Mul( ivf[ i ] , i ); 
}
int C( int n , int m ) { return Mul( fac[ n ] , Mul( ivf[ m ] , ivf[ n - m ] ) ); }
int Calc( int n , int m ) { return n < 0 || m < 0 ? 0 : C( n + m , n ); }

int n , m;
pii upd1( pii x ) { return mp( x.sc - 1 , x.fi + 1 ); } //以 y = x + 1 
pii upd2( pii x ) { return mp( x.sc + ( m + 2 ) , x.fi - ( m + 2 ) ); } //以 y = x - (m+2) 

int main( ) {
	Init();
	
	scanf("%d %d",&n,&m);
	int Ans = C( n + m + 1 + n , n );
	for( pii t = mp( n + m + 1 , n ) ; t.fi >= 0 && t.sc >= 0 ; ) {
		t = upd1( t ); Ans = Sub( Ans , Calc( t.fi , t.sc ) );
		t = upd2( t ); Ans = Add( Ans , Calc( t.fi , t.sc ) );
	}
	for( pii t = mp( n + m + 1 , n ) ; t.fi >= 0 && t.sc >= 0 ; ) {
		t = upd2( t ); Ans = Sub( Ans , Calc( t.fi , t.sc ) );
		t = upd1( t ); Ans = Add( Ans , Calc( t.fi , t.sc ) );
	}
	printf("%d\n", Ans );
	return 0;
} 
上一篇:py学习记录#11


下一篇:题解-八省联考2018 林克卡特树