Just Jump

Posted on | In , , ,

题目链接

题意

一只青蛙从$1$跳到$L$位置，每次向前至少跳$d$步，最后一次要求恰好跳到$L$，且有$m$个限制，第$i$次跳跃不能跳到。询问合法跳跃方案数。

思路

很容易想到一个动态规划加容斥的思路，dp计算出不考虑限制的方案数，然后容斥不合法的。
但是不能暴力容斥。
考虑我们的容斥也像dp那样记忆化一下。用$dp[i]$表示第$i$次限制作为容斥子集的容斥结果，我们可以枚举他前面一个在子集中元素。
（其实这种方法是很常用的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e7+10;
const int mod=998244353;
int n,m,t,L,d,b[N],dp[N],sum[N],fac[N],facv[N];
pair<int,int>a[3005];
int quickpow(ll a,ll b){
     int ans=1;
     a%=mod;
     while(b){
        if(b&1)ans=1ll*ans*a%mod;
        a=1ll*a*a%mod;
        b>>=1;
     }
     return ans%mod;
}
void init(){
    fac[0]=facv[0]=1;
    for(int i=1;i<N;i++)fac[i]=1ll*fac[i-1]*i%mod;
    facv[N-1]=quickpow(fac[N-1],mod-2);
    for (int i=N-1;i;i--)facv[i-1]=1ll*facv[i]*i%mod;
}
int C(int x,int y){
    if(x<y) return 0;
    return 1ll*fac[x]*facv[y]%mod*facv[x-y]%mod;
}
int solve(int l,int r){
    if(a[l].second>=a[r].second||a[l].first==a[r].first)return 0;
    int len=a[r].first-a[l].first,tm=a[r].second-a[l].second;
    if (1ll*tm*d-len>0) return 0;
    return C(len-tm*d+tm-1,tm-1);
}
int main(){
    init();
    scanf("%d%d%d",&L,&d,&m);
    for(int i=1;i<=m;i++)scanf("%d%d",&a[i].second,&a[i].first);
    sort(a+1,a+m+1);
    sum[0]=b[0]=1;
    for(int i=1;i<d;i++)sum[i]=sum[i-1];
    for(int i=d;i<=L;i++){
        dp[i]=sum[i-d];
        sum[i]=(sum[i-1]+dp[i])%mod;
    }
    for(int i=1;i<=m;i++){
        for(int j=0;j<i;j++)b[i]=(b[i]+1ll*b[j]*solve(j,i)%mod)%mod;
        b[i]=(mod-b[i])%mod;
    }
    for(int i=1;i<=m;i++)dp[L]=(dp[L]+1ll*b[i]*dp[L-a[i].first]%mod)%mod;
    printf("%d\n",dp[L]);
    return 0;
}

0%