格路计数

$[x,y]_{a_1,a_2\cdots}^{b_1,b_2\cdots}$：每一步可以为 $(1,1)$ 或 $(1,-1)$，从 $(0,0)$ 走到 $(x,y)$，必须与 $y=a_1,y=a_2\cdots$ 相交，不能与 $y=b_1,y=b_2\cdots$ 相交的路径数。

规定 $x\ge 0,y\ge 0$，$a_1\le a_2\le\cdots,b_1\le b_2\le\cdots$。

1. 无限制路径数

   $$[x,y]=\begin{cases} 0&(x<y\lor x\not\equiv y\pmod{2})\\ \dbinom{x}{\frac{x+y}{2}}&(\text{else})\\ \end{cases}$$

   $x<y\lor x\not\equiv y\pmod{2}$ 判为 $0$ 对于求任意限制的路径数均可使用。

2. 有一条必经直线的路径数

   $$[x,y]_k=\begin{cases} [x,y]&(0\le k\le y)\\ [x,-2k+y]&(k<0)\\ [x,2k-y]&(k>y)\\ \end{cases}$$

3. 有一条不可经过直线的路径数

   $$[x,y]^k=[x,y]-[x,y]_k$$

4. 有上下界的路径数

   求有上下界的路径数在递归过程中还需求有必经下界，不可经过上界的路径数。

   下文中规定 $k_1<0,k_2>0$。

   $$[x,y]_{k_1}^{k_2}=\begin{cases} 0&(x<y-2k_1)\\ [x,y-2k_1]^{-k_2,k_2-2k_1}+[x,y]_{2k_1-k_2}^{k_2}&(\text{else})\\ \end{cases}$$

   $$[x,y]^{k_1,k_2}=\begin{cases} [x,y]^{k_2}&(x<y-2k_1)\\ [x,y]-[x,y]_{k_2}-[x,y]_{k_1}^{k_2}&(\text{else})\\ \end{cases}$$

   求 $[x,y]^{k_1,k_2}$ 的时间复杂度最优为 $O(1)$，最劣为 $O(x)$。

注意事项：无。

代码：

int d1(int x, int y) {
    if ((x < y) || ((x & 1) != (y & 1))) return 0;
    return C(x, (x + y) / 2);
}
int d2(int x, int y, int k) {
    if (k >= 0 && k <= y) return d1(x, y);
    else if (k < 0) return d1(x, -2 * k + y);
    else return d1(x, 2 * k - y);
}
int d3(int x, int y, int k) {
    return redmod(d1(x, y) - d2(x, y, k));
}
int d5(int, int, int, int);
int d4(int x, int y, int k1, int k2) {
    if (x < y - 2 * k1) return 0;
    else return addmod(d5(x, y - 2 * k1, -k2, k2 - 2 * k1) + d4(x, y, 2 * k1 - k2, k2));
}
int d5(int x, int y, int k1, int k2) {
    if (x < y - 2 * k1) return d3(x, y, k2);
    else return redmod(redmod(d1(x, y) - d2(x, y, k2)) - d4(x, y, k1, k2));
}

Luogu P3266 [JLOI2015]骗我呢

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXn = 1e6;
const int MAXm = 1e6;
const int MOD = 1e9 + 7;

template <typename T>
inline void read(T &a) {
    char c;for (c = getchar(); (c < '0' || c > '9') && c != '-'; c = getchar());bool f = c == '-';T x = f ? 0 : (c ^ '0');for (c = getchar(); c >= '0' && c <= '9'; c = getchar()) {x = x * 10 + (c ^ '0');}a = f ? -x : x;
}
template <typename T, typename ...Argv>
inline void read(T &a, Argv &...argv) {
    read(a), read(argv...);
}

inline int addmod(int x) {
    return (x >= MOD) ? x - MOD : x;
}
inline int redmod(int x) {
    return (x < 0) ? x + MOD : x;
}

const int MAXfac = MAXn * 2 + MAXm + 1;
int fac[MAXfac + 10], invfac[MAXfac + 10];
void evafacinvfac(int n) {
    fac[0] = invfac[0] = fac[1] = invfac[1] = 1;
    for (int i = 2; i <= n; ++i) {
        fac[i] = fac[i - 1] * i % MOD;
    }
    for (int i = 2; i <= n; ++i) {
        invfac[i] = (MOD - MOD / i) * invfac[MOD % i] % MOD;
    }''
	for (int i = 2; i <= n; ++i) {
		invfac[i] = invfac[i] * invfac[i - 1] % MOD;
	}
}
inline int C(int n, int m) {
	return fac[n] * invfac[m] % MOD * invfac[n - m] % MOD;
}
int d1(int x, int y) {
	if ((x < y) || ((x & 1) != (y & 1))) return 0;
	return C(x, (x + y) / 2);
}
int d2(int x, int y, int k) {
	if (k >= 0 && k <= y) return d1(x, y);
	else if (k < 0) return d1(x, -2 * k + y);
	else return d1(x, 2 * k - y);
}
int d3(int x, int y, int k) {
	return redmod(d1(x, y) - d2(x, y, k));
}
int d5(int, int, int, int);
int d4(int x, int y, int k1, int k2) {
	if (x < y - 2 * k1) return 0;
	else return addmod(d5(x, y - 2 * k1, -k2, k2 - 2 * k1) + d4(x, y, 2 * k1 - k2, k2));
}
int d5(int x, int y, int k1, int k2) {
	if (x < y - 2 * k1) return d3(x, y, k2);
	else return redmod(redmod(d1(x, y) - d2(x, y, k2)) - d4(x, y, k1, k2));
}

int n, m;
signed main() {
	read(n, m);
	evafacinvfac(n * 2 + m + 1);
	printf("%lld\n", d5(2 * n + m + 1, m + 1, -1, m + 2));
	return 0;
}