2019牛客暑期多校第八场 Just Jump

题意

数轴上，从0跳到n，其中有n-1个石头，每次至少跳d米，还有m个限制， $(t_{i}, p_{i})$ 表示不能第 $t_{i}$ 次跳到 $p_{i}$ 的位置，求方案数

题解

先不考虑限制，转移方程为 $f [i] = f [0] + f [1] + \dots + f [i - d]$
考虑限制
根据容斥，我们知道，总方案数，减去被1个限制的方案数，加上被2个限制的方案数，减去被3个限制的方案数，加上被4个限制的方案数…就是答案
考虑一个限制为 $(t_{i}, p_{i})$ , 从位置0走到 $p_{i}$ 且是第 $t_{i}$ 次跳到的方案数为 $C_{p_{i} - d \times t_{i} + t_{i} - 1}^{t_{i} - 1}$
原理就是n个球放m个盒子，盒子不同，能为空
从 $p_{i}$ 跳到n的方案数就是 $f [n - p_{i}]$
暴力枚举的话，复杂度为 $2^{3000}$ ，显然不能接受
考虑枚举出一种情况，假设有 k 个限制，根据 k 的奇偶来决定是加还是减
首先这必须是一个合法情况，即按照 $t_{i}$ 排序后， $p_{i}$ 也是升序，相邻 $p_{i}$ 大于等于 d
我们可以套用上面的公式求出方案数
具体来说， $0 - p_{q_{1}}, p_{q_{1}} - p_{q_{2}}, . . ., p_{q_{k - 1}} - p_{q_{k}}$ 套用 $C_{p_{i} - d \times t_{i} + t_{i} - 1}^{t_{i} - 1}$ ， $p_{q_{k}} - n$ 套用 $f [n - p_{i}]$ ，这是显然的
现在考虑加上一个限制，不妨设在 $p_{q_{k}}$ 的后面，设为 $q_{k + 1}$
发现可以利用之前的答案 $O (1)$ 求解

注意到，加一个限制，做一次遍历(3000)即可，而总共有3000个限制，到这里，发现似乎可以在平方级别的复杂度内实现求解
首先按照 $t$ 对所有限制进行排序
考虑 $g [u] [0 / 1]$ 表示，到第 u 个限制，总限制为偶数/奇数的方案数
而由于排序，能转移到 u 的必然在 u 的前面，满足了无后效性
所以，枚举 u 之前的限制，奇偶相互统计即可

代码

#include<bits/stdc++.h>
#define N 10000010
#define INF 0x3f3f3f3f
#define eps 1e-8
#define pi 3.141592653589793
#define mod 998244353
#define P 1000000007
#define LL long long
#define pb push_back
#define fi first
#define se second
#define cl clear
#define si size
#define lb lower_bound
#define ub upper_bound
#define bug(x) cerr<<#x<<" : "<<x<<endl
#define mem(x) memset(x,0,sizeof x)
#define sc(x) scanf("%d",&x)
#define scc(x,y) scanf("%d%d",&x,&y) 
#define sccc(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
typedef pair<int,int> pp;

int n,m,h,d,T;
LL fac[N],inv[N],g[3010][2];
int f[N];
pp w[3010];

LL qpow(LL a,LL b){
    LL res=1;
    while(b){
        if (b&1) res=res*a%mod;
        b>>=1;
        a=a*a%mod;
    } 
    return res;
}

LL C(int n,int m){
    return fac[n]*inv[m]%mod*inv[n-m]%mod;
}

inline void add(LL &a,LL b){
    a+=b;
    if (a>=mod) a-=mod;
}

int main(int argc, char const *argv[]){
    sccc(n,d,m);
    fac[0]=1;
    for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
    inv[n]=qpow(fac[n],mod-2);
    for(int i=n-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
    f[0]=1;
    for(int i=d,s=0;i<=n;i++)s=(s+f[i-d])%mod,f[i]=s;
    LL ans=f[n];
    for(int i=1;i<=m;i++) scc(w[i].fi,w[i].se);
    sort(w+1,w+m+1);
    g[0][0]=1;
    for(int i=1;i<=m;i++){
        for(int j=0;j<i;j++) {
            LL dis=w[i].se-w[j].se,p=w[i].fi-w[j].fi;
            if (dis-p*d<0 || p<=0 ) continue;
            LL t=C(dis-p*d+p-1,p-1);
            add(g[i][0],g[j][1]*t%mod);
            add(g[i][1],g[j][0]*t%mod);
        }
        ans=(ans+(g[i][0]-g[i][1]+mod)%mod*f[n-w[i].se]%mod)%mod;
    }
    cout<<ans;
    return 0;
}