题解：Just Jump

Just Jump

题意：

有 \(L+1\) 个石头，起点为 \(0\)，终点为 \(L\)，初试时间为零秒，每秒可以从石头 \(i\) 移动到石头 \(j\) 仅当 \(j-i\ge d\)，且不能停留在一个石头上，有 \(m\) 个事件，第 \(i\) 个事件中，第 \(p_i\) 个石头（不包括起点与终点）在 \(t_i\) 秒会被攻击，此时不能站在该石头上。问从起点刚好跳到终点的方案数。

\(1\le L,d\le 10^7,1\le t_i,p_i\le L,1\le m\le 3\times 10^3\)

考虑容斥，答案为所有从 \(0\) 走到 \(L\) 的方案数减去其中经过被攻击的石头的路径的方案数。

首先对所有被攻击的石头按编号从小到大排序，设 \(dp_i\) 表示经过第 \(i\) 个石头的路径的方案数。

由于被攻击的石头可以从 \(0\) 走到与到达 \(L\)，因此简单起见，我们把 \(0\) 和 \(L\) 也认定为会被攻击的石头，并把 \(0\) 作为在 \(0\) 秒是会被攻击参与排序，\(L\) 由于没有时间约束单独处理，排序后 \(0\) 编号为 1，\(L\) 为 \(m+2\)。

考虑被攻击的石头 \(p_i\) 走到另一个被攻击的石头 \(p_j\) 的方案数，其时间差 \(k=t_j-t_i\)，距离为 \(x=p_j-p_i\)，\(p_i\) 可以走到 \(p_j\) 仅当 \(k> 0\) 且 \(x \ge k\times d\)。

对于满足要求的 \(p_i,p_j\)，可以走 \(k\) 步，假设每走的距离都为 \(d\)，那么还剩下 \(n=x-k\times d\) 的距离，将其分配到 \(k\) 步中，就是求非负整数和的数目了。通过插板法可以得到方案数为：

\[f(n,k)=\begin{pmatrix}n+k-1 \\k-1 \\ \end{pmatrix} \]

因此可以得到转移方程：

\[dp_i=-\sum_{j=1}^{i - 1}\begin{pmatrix} n+k-1 \\ k-1 \\ \end{pmatrix}dp_j\]

对于位置 \(L\)，对于每个 \(p_i\)，其到 \(L\) 的距离为 \(x=L-p_i\)，但时间不限，因此方案数为：

\[S(x)=\sum_{k=1}^{\lfloor\frac{x}{d}\rfloor}f(x-k\times d,k) \]

若 \(x<d\) 则 \(S(x)=0\)。

由于 \(d\) 是定值，因此我们可以递推求出 \(S(x)\)。

我们带入 \(f(n,k)\) 的式子并化简变换可以得到：

\[S(x)=\sum_{k=0}^{\lfloor\frac{x-d}{d}\rfloor}\begin{pmatrix} x-d - k(d-1) \\ k \\ \end{pmatrix}\]

DeepSeek 非常抽象地帮我把上面这个式子带入到生成函数中：

\[F(x)=\sum_{i\ge0}S(i)x^i=\frac{x^d}{1-x-x^d} \]

然后宣布得出递推关系：

\[S(x)=S(x-1)+S(x-d) \]

因而对于位置 \(i\) 到位置 \(L\) 距离为：

\[S(L-p_i)dp_i \]

对于 \(0\) 到 \(L\) 的方案数显然为 \(S(L)\)

因此通过容斥得到答案为：

\[S(L)+\sum_{i=2}^{m+1}S(L-p_i)dp_i \]

代码：

#include<bits/stdc++.h>
#define cin_fast ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0)
#define fi first
#define se second
//#define int long long 
#define in(a) a = read()
#define rep(i , a , b) for(int i = a ; i <= b ; i ++)
using namespace std;
typedef long long ll;
const int N = 1e5 + 5 , mod = 998244353;
const int inf = 0x3f3f3f3f;
const long long INF = 0x3f3f3f3f3f3f3f3f; 
inline int read() {int x = 0;char ch = getchar();bool f = 0;while('9' < ch || ch < '0') f |= ch == '-' , ch = getchar();while('0' <= ch && ch <= '9') x = (x << 3) + (x << 1) + ch - '0' , ch = getchar();return f ? -x : x;
}
ll qpow(ll x , ll y) {ll ans = 1;for(; y ; x = (x * x) % mod , y >>= 1) if(y & 1) ans = (ans * x) % mod;return ans;
}
ll jc[20000005] , s[20000005];
ll C(ll n , ll m) {if(n < m || n < 0 || m < 0) return 0;if(m == 0) return 1;return (jc[n] * qpow((jc[m] * jc[n - m]) % mod , mod - 2)) % mod;
}
struct node{int t , p;
}a[N];
ll dp[N];
bool cmp(node x , node y) {if(x.p == y.p) return x.t < y.t;return x.p < y.p;
}
signed main() {//cin_fast;ll L , d , m;in(L) , in(d) , in(m); for(int i = 1 ; i <= m ; i ++) in(a[i].t) , in(a[i].p);jc[0] = 1;for(int i = 1 ; i <= L + L ; i ++) jc[i] = (jc[i - 1] * i) % mod;s[d] = 1;for(int i = d + 1 ; i <= L + L ; i ++) s[i] = (s[i - 1] + s[i - d]) % mod;a[++ m] = {0 , 0};sort(a + 1 , a + m + 1 , cmp);dp[1] = 1;for(int i = 2 ; i <= m ; i ++) {int x2 = a[i].t , y2 = a[i].p;for(int j = 1 ; j < i ; j ++) {int x1 = a[j].t , y1 = a[j].p;ll k = x2 - x1 , n = y2 - y1;if(k <= 0 || n < k * d) continue;n -= k * d;ll w = C(n + k - 1 , k - 1);dp[i] += (w * dp[j]) % mod;dp[i] %= mod;}dp[i] = mod - dp[i];}ll ans = s[L]; for(int i = 2 ; i <= m ; i ++) {dp[i] = (dp[i] * s[L - a[i].p]) % mod;ans = (ans + dp[i]) % mod;}cout << ans;return 0;
}