2019牛客多校-8J-Just Jump（组合数+容斥原理）

Just Jump

题意：
求从 $0$0跳到 $L$L处的方案数，条件限制为：
—每次跳跃最少跳 $d$d的长度
—有 $m$m个 $pair(t,p)$pair(t,p)，每个表示不能在跳第 $t$t次时跳到点 $p$p处

思路：

1. 利用容斥原理，先求出从 $0$0跳到 $L$L处的总方案，然后减去满足某个 $pair$pair的所有方案，再加上满足某两个 $pair$pair的所有方案，再减去 $......$......，加上 $......$......， $......$......
2. 首先，从 $0$0跳到 $L$L处的总方案可以 $O\left(n\right)$O(n)的进行预处理
3. 然后将所有的 $pair$pair按照 $pair\&lt;int,int\&gt;$pair<int,int>形式进行排序，排序的目的在于使前面的 $pair$pair经历与否都不会影响后面的方案数
4. 我们设定一个 $dp\left[maxn\right]\left[2\right]$dp[maxn][2]，其中 $dp\left[i\right]$dp[i]的第二维表示 $i$i是第偶数个还是奇数个经历的 $pair$pair，因为容斥原理处每个方案是第。。。后面再更吧

题目描述

//#pragma comment(linker, "/STACK:102400000,102400000")
#include "bits/stdc++.h"
#define pb push_back
#define ls l,m,now<<1
#define rs m+1,r,now<<1|1
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}

const int maxn = 1e7+10;
const int mod = 998244353;
const double eps = 1e-9;

struct P{
	int t, p;
	bool operator < (const P &rhs) const {
		if(t==rhs.t) return p<rhs.p;
		return t<rhs.t;
	}
}p[3001];

int L, d, m;
ll fac[maxn], inv[maxn], s[maxn], a[maxn], dp[3001][2];

void initp() {
	fac[0]=fac[1]=inv[0]=inv[1]=1;
	for(int i=2; i<maxn; ++i) {
		fac[i]=fac[i-1]*i%mod;
		inv[i]=inv[mod%i]*(mod-mod/i)%mod;
	}
	for(int i=2; i<maxn; ++i)
		inv[i]=inv[i]*inv[i-1]%mod;
}

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

ll cal(int t, int p) {
	if(t<=0||p<=0||1ll*t*d>p) return 0;
	return C(int(p-1ll*t*d+t-1),t-1);
}

int main() {
	//ios::sync_with_stdio(false);
	initp();
	cin>>L>>d>>m; a[0]=s[0]=1;
	for(int i=1; i<=L; ++i) a[i]=i>=d?s[i-d]:0, s[i]=(s[i-1]+a[i])%mod;
	for(int i=1; i<=m; ++i) p[i]=(P){read(),read()};
	sort(p+1,p+1+m);
	ll ans=a[L]; dp[0][0]=1;
	for(int i=1; i<=m; ++i) {
		for(int j=0; j<i; ++j) {
			for(int k=0; k<2; ++k) {
				(dp[i][k]+=dp[j][k^1]*cal(p[i].t-p[j].t,p[i].p-p[j].p))%=mod;
			}
		}
		(ans+=(dp[i][0]+(mod-1)*dp[i][1])%mod*a[L-p[i].p]%mod)%=mod;
	}
	cout<<ans<<endl;
}