bzoj4402: Claris的剑

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#define ll long long
#define N 2000006
#define P 1000000007

using namespace std;
int pow2(int x,int y){
	int ret=1;
	while (y){
		if (y&1) ret=(ll)ret*x%P;
		x=(ll)x*x%P;
		y=y>>1;
	}
	return ret;
}

int fact[N],fm;
int c(int n,int m){
	if (n<m) return 0;
	return (ll)fact[n]*fm%P*pow2(fact[n-m],P-2)%P;
}
int n,m;

int main(){
	scanf("%d%d",&n,&m);
	if (m<2||n<2){printf("%d\n",max(m,0));return 0;}
	for (int i=fact[0]=1;i<=n/2+m/2+3;++i) fact[i]=(ll)fact[i-1]*i%P;
	int ans=2,now[2]={1,0};
	fm=pow2(fact[m-2],P-2);
	for (int i=3;i<=n;++i){
		(now[i&1]+=now[1^i&1])%=P;
		if ((i-m-1)%2==0) (now[1^m&1]-=c((i-m-1)/2+m-2,m-2)-P)%=P;
		(ans+=(now[0]+now[1])%P)%=P;
	}
	printf("%d\n",ans);
	return 0;
}