牛客第八场 J Just Jump —— 思维dp + 组合数

题目链接：点我啊╭(╯^╰)╮

题目大意：

    $L$ 块石头，每次至少跳 $d$ 步，从 $0$ 跳到 $L$
    $m$ 次攻击，在 $t_i$ 这个时间不能在 $p_i$ 位置上
    求所有的方案数？？？

解题思路：

    不考虑攻击
    设 $f[i]$ 为跳到位置 $i$ 的方案数
    $f[i]={\sum }_{j=0}^{i?d}f[j]$
    则可在 $O(L)$ 的时间内求出 $f[i]$

    考虑一次攻击 $(t,p)$
    从 $0$ 跳 $t$ 次到位置 $p$ 的方案数，等同于放球问题
    相当于 $p$ 个球放入 $t$ 个盒子里，盒子互不相同，球相同
    根据隔板法，方案数为 $C_{p+t?1}^p$
    加入每次至少跳 $d$ 步的限制，等同于少了 $dt$ 个球
    方案数为 $C_{p?dt+t?1}^{p?dt}=C_{p?dt+t?1}^{t?1}$
    从 $p$ 跳到 $L$ 的方案数，等于从 $0$ 跳到 $L?p$ 的方案数 $f[L?p]$
    则一次攻击的贡献为 $C_{p?dt+t?1}^{t?1}\times f[L?p]$

    考虑多次攻击
    因为每次攻击的贡献只能是它作为第一次攻击时的方案数
    所以计算第 $k$ 次攻击时，要减去前 $k?1$ 次攻击作为第一次攻击、第 $k$ 次攻击作为第二次攻击的方案数
    设 $dp[i]$ 表示第 $i$ 次攻击，从 $0$ 跳 $t_i$ 次到 $p_i$ 的方案数
    $dp[i]=C_{p_i?d{t}_i+t_i?1}^{t_i?1}?{\sum }_{j=1}^{i?1}{C}_{p_i?p_j?d(t_i?t_j)+t_i?t_j?1}^{t_i?t_j?1}\times dp[j]$
    也就是减去从 $0$ 跳 $t_i?t_j$ 次到位置 $p_i?p_j$ 的方案数
    也就得出了第 $i$ 次攻击作为第一次攻击的前半部分贡献了

    最后答案就是：
    $ans=f[L]?{\sum }_{i=1}^{m}dp[i]\times f[l?p_i]$

    时间复杂度（预处理逆元）：$O(L+m^2)$

核心：思维dp与组合数的运用

#include<bits/stdc++.h>
#define rint register int
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
using namespace std;
typedef long long ll;
typedef pair <int,int> pii;
const ll mod = 998244353;
const int maxn = 1e7 + 5;
int m;
ll l, d;
ll dp[3005], f[maxn], sum[maxn];struct node{ll t, p;bool operator < (const node &A){return t < A.t; }
} a[3005];const int maxf = 1e7 + 5;
ll fac[maxf], inv[maxf], invf[maxf];
void init(){fac[0] = inv[0] = invf[0] = 1;fac[1] = inv[1] = invf[1] = 1;for(rint i=2; i<maxf; i++){fac[i] = fac[i-1] * i % mod;inv[i] = (mod - mod / i) * inv[mod % i] % mod;invf[i] = inv[i] * invf[i-1] % mod;}
}ll C(ll n, ll m){if(n<0 || m<0 || n<m) return 0;return fac[n] * invf[m] % mod * invf[n-m] % mod;
}int main() {init();scanf("%lld%lld%d", &l, &d, &m);for(int i=1; i<=m; i++) scanf("%lld%lld", &a[i].t, &a[i].p);sum[0] = 1;for(int i=1; i<=l; i++){if(i < d) f[i] = 0;else f[i] = sum[i-d] % mod;sum[i] = (sum[i-1] + f[i]) % mod;}sort(a+1, a+1+m);ll ans = f[l];for(int i=1; i<=m; i++){ll pi = a[i].p, ti = a[i].t;dp[i] = C(pi-1ll*d*ti+ti-1, ti-1);for(int j=1; j<i; j++){ll pj = a[j].p, tj = a[j].t;dp[i] = dp[i] - dp[j] * C(pi-pj-1ll*d*(ti-tj)+ti-tj-1, ti-tj-1) % mod;dp[i] = (dp[i] + mod) % mod;}ans = (ans - dp[i] * f[l - pi] % mod + mod) % mod;}printf("%lld\n", ans);
}