题解
我深思熟虑许久才算是明白个大概的计数问题吧
先是转化成一个矩形，列一条直线y = x,y = x - (m + 1)我们从(0,0)走到(n + m + 1,m + 1)就是答案
因为我们起始相当于第一行缺一个0，然后有m+1种转移的方案，每次在距左边界j的地方某个点向上走表示转移到缺j - 1，向右走一步走到了缺j，再走一步走到缺j + 1....
我们把向上走当做-1，向右走当做+1，我们可以建立一个新的模型
就是起点为((0,0))终点为((2 * n + m + 1,m + 1))，每次可以走到((x + 1,y + 1))或者走到((x + 1,y - 1))
不能碰到(y = -1)或者(y = m + 2)
我们要用总方案去掉碰到(y = -1)和碰到(y = m + 2)再加上两个都碰到的
我们对于碰到(y = -1)我们就关于让终点关于(y = -1)对称，求原点到那里的方案数，因为每条不合法的路径对应一条到翻折点的路径在和(y = -1)第最后一个交点处后的路径沿(y = -1)翻折即可
我们把两个都碰到的拆成最后一个碰到的是(y = -1)记为A和第最后一个碰到的是(y = m + 2)记为B
举个例子
我们对于(y = -1)统计第最后碰到的是A
对于一条需要被加上的路径（也就是影响需要被抵消的路径）
经历的顺序记为
ABABA
那么我们
去掉了后缀为AB 和A 的
再加上后缀为AB 和 ABA的
再减去后缀为ABA 和 ABAB的
直到不能计算了为止
怎么计算后缀为AB 和 ABA的两种情况呢
我们把(y = m + 2)对着(y = -1)再次翻折，把(n * 2 + m + 1,m + 1)这个点对着(y = -1)翻折后，再次对着(y = -m - 4)翻折
计算(0,0)到目标点的答案就是我们想要的
最后我们只要把直线不断翻折直到不能达成为止
我们再对(y = m + 1)做相同的操作即可
这道题要是考场上给我，我也只能写60分暴力滚粗了……
代码
#include <bits/stdc++.h>
#define enter putchar('
')
#define space putchar(' ')
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eps 1e-8
#define MAXN 4000005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned long long u64;
typedef double db;
template<class T>
void read(T &res) {
res = 0;T f = 1;char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 - '0' + c;
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {x = -x;putchar('-');}
if(x >= 10) out(x / 10);
putchar('0' + x % 10);
}
const int MOD = 1000000007;
int inc(int a,int b) {
return a + b >= MOD ? a + b - MOD : a + b;
}
int mul(int a,int b) {
return 1LL * a * b % MOD;
}
int fac[MAXN],invfac[MAXN],inv[MAXN],N,M,ans,x;
int C(int n,int m) {
if(n < m) return 0;
return mul(fac[n],mul(invfac[m],invfac[n - m]));
}
int F(int n,int m) {
return C(n,(n - m) / 2);
}
void Calc(int y,int y_1,int y_2) {
while(1) {
y = 2 * y_1 - y;
y_2 = 2 * y_1 - y_2;
if(abs(y) > x) break;
ans = inc(ans,MOD - F(x,y));
y = 2 * y_2 - y;
y_1 = 2 * y_2 - y_1;
if(abs(y) > x) break;
ans = inc(ans,F(x,y));
}
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
read(N);read(M);
inv[1] = 1;
for(int i = 2 ; i <= 4000000 ; ++i) inv[i] = mul(inv[MOD % i],MOD - MOD / i);
fac[0] = invfac[0] = 1;
for(int i = 1 ; i <= 4000000 ; ++i) {
fac[i] = mul(fac[i - 1],i);
invfac[i] = mul(invfac[i - 1],inv[i]);
}
x = 2 * N + M + 1;
ans = inc(ans,F(x,M + 1));
Calc(M + 1,-1,M + 2);Calc(M + 1,M + 2,-1);
out(ans);enter;
}