Teleporting Takahashi
题意
起点是 \((0, 0, 0)\), 给出终点 \((x,y,z)(-10^7\leq x,y,z \leq 10^7)\) 和 \(n (\leq 10^7)\) 步，每步只能在一维 \(+1 / -1\), 求不同的行走方案数，对 \(998244353\) 取模。
分析
小小的转化，对于 \(x,y,z\) 中小于 0 的，变为整数，显然结果不会改变。
那么 \(x, y, z \geq 0\)
先考虑无解的情况：
-
步数不够，\(x + y + z > n\)。
-
多的步数不能消耗 \(x + y + z \equiv 1 \pmod 2\)。
先考虑两维 \((x, y)\)。
设 \(k\), 表示这两位走了 \(x + y + 2k\) 步。
求这样的方案数，枚举 \(i\) 表示 \(x\) 多的 \(+1\) 操作个数, 也就有 \(i\) 个 \(-1\) 操作。
\(y\) 多出 \(k - i\) 个 \(+1\) 和 \(-1\) 操作。
那么就有这样的式子:
\[\sum_{i = 0}^{k} \binom{x + y + 2k}{x + i, i, y + k - i, k - i} \]重新考虑这 \(x + y + 2k\) 的分配，先分开 \(+1\) 和 \(- 1\) 操作, 在考虑对两部分分配。
于是就有:
\[\sum_{i = 0}^{k} \binom{x + y + 2k}{x + y + k} \binom{x + y + k}{x + i} \binom{k}{i} \]\[\binom{x + y + 2k}{x + y + k}\sum_{i = 0}^{k} \binom{x + y + k}{x + i} \binom{k}{k - i} \]根据范德蒙德恒等式，
\[\binom{n + m}{k} = \sum_{i = 0}^{k} \binom{n}{k} \binom{m}{k - i} \]就有：
\[\binom{x + y + 2k}{x + y + k}\binom{x + y + 2k}{x + k} \]记做 \(F_k\)。
在考虑第三维，枚举步数 \(2i\) 给它，\(K\) 是多出的总步数。
于是答案就是
\[\sum_i^{K} \binom{n}{z + 2i}\binom{z + 2i}{z + i}F_{K - k} \]代码
#include
using namespace std;
using ll = long long;
const int MAXN = 10000010;
const int INF = 0x7fffffff;
const int mod = 998244353;
template
void Read(T &x) {
x = 0; T f = 1; char a = getchar();
for(; a < '0' || '9' < a; a = getchar()) if (a == '-') f = -f;
for(; '0' <= a && a <= '9'; a = getchar()) x = (x * 10) + (a ^ 48);
x *= f;
}
int add(int a, int b) {
int c = a + b;
if (c >= mod) c -= mod;
if (c < 0) c += mod;
return c;
}
int mul(int a, int b) {
return 1ll * a * b % mod;
}
int qpow(int a, int b) {
int sum(1);
while (b) {
if (b & 1) sum = mul(sum, a);
a = mul(a, a);
b >>= 1;
}
return sum;
}
int f[MAXN], ifa[MAXN];
void pre(int n) {
f[0] = 1;
for (int i = 1; i <= n; i ++)
f[i] = mul(f[i - 1], i);
ifa[n] = qpow(f[n], mod - 2);
for (int i = n - 1; i >= 0; i --)
ifa[i] = mul(ifa[i + 1], i + 1);
}
int C(int n, int m) {
if (n < m || n < 0 || m < 0) return 0;
return mul(mul(f[n], ifa[m]), ifa[n - m]);
}
int n, x, y, z;
int F(int k) {
return mul(C(x + y + 2 * k, x + y + k), C(x + y + 2 * k, k + y) );
}
int main() {
ios::sync_with_stdio(false);
cin >> n >> x >> y >> z;
if (x < 0) x = - x;
if (y < 0) y = - y;
if (z < 0) z = - z;
if (x + y + z > n || (n - x - y - z) & 1) return cout << 0, 0;
pre(n);
int ans = 0, k = (n - x - y - z) / 2;
for (int i = 0; i <= k; i ++) {
ans = add(ans, mul(mul(C(n, z + i * 2), C(z + i * 2, z + i)), F(k - i)));
}
cout << ans;
return 0;
}