题意
有一条长为L LL的河，你在位置0 00你要通过这条长为L LL的河到达L LL，河中从Unexpected text node: ' 'Unexpected text node: ' '1,2,3,⋯,L−1有石子可以踩上去通过，你每一次所走的距离必须要大于等于d dd，并且还存在m mm次攻击，每一次攻击由二元组(ti,pi) (t_i,p_i)(t
i
,p
i
)组成，表示，在ti t_it
i
次跳跃时落在pi p_ip
i
时你就会被攻击，若被攻击你就会失败，求从0 00出发到达L LL的方法数
思路
先考虑没有攻击时总的方案数，有
f[i]=f[1]+f[2]+f[3]+⋯+f[i−d] f[i]=f[1]+f[2]+f[3]+\cdots+f[i-d]
f[i]=f[1]+f[2]+f[3]+⋯+f[i−d]
f[i+1]=f[1]+f[2]+f[3]+⋯+f[i−d]+f[i+1−d] f[i+1]=f[1]+f[2]+f[3]+\cdots+f[i-d]+f[i+1-d]
f[i+1]=f[1]+f[2]+f[3]+⋯+f[i−d]+f[i+1−d]
可以发现我们要是每次维护一个前缀和就可以O(1) O(1)O(1)求得的f[i] f[i]f[i]
f[i]=sum[i−1−d]+f[i−d] f[i]=sum[i-1-d]+f[i-d]
f[i]=sum[i−1−d]+f[i−d]
所以可以在O(L) O(L)O(L)的时间求的总的方法数f[L] f[L]f[L]
那么最终的答案我们可以考虑用f[L] f[L]f[L]去减去被攻击时的方案数，就是最终的答案。
我们考虑一下每一个(t,p) (t,p)(t,p)的贡献，可以分成两部分考虑
从0 00跳t tt次到达p pp，那么我们先考虑没有每次至少跳d dd步的限制，那么就是从0 00到p pp，跳t tt次，每次可以跳任意步数。转换一下可以变为有p pp个球，放到t tt个箱子里，箱子可以为空的方案数，那就可以套用经典的隔板法那么答案就是Ct−1p+t−1 C_{p+t-1}^{t-1}C
p+t−1
t−1
。现在有了每次至少跳d dd的限制那么我们可以在一开始p−dt p-dtp−dt，那么剩下的这段距离就是原来的无限制的方案数了，那么方案数就是
Ct−1p−dt+t−1 C_{p-dt+t-1}^{t-1}
C
p−dt+t−1
t−1
从p pp跳到L LL的方案数，这段的方案数其实和从0 00跳到L−p L-pL−p是等价，那么方案数就是f[L−p] f[L-p]f[L−p]
那么每一个攻击的贡献就是这两部分的方案数之积了，解决了某一个攻击的贡献，我们还要考虑一下攻击和攻击之间的关系。我们可以先把攻击按照跳的次数排个序，由于题目中跳跃的次数是没有重复的，我们通过排序后，令dp[i] dp[i]dp[i]为跳ti t_it
i
次第一次被攻击时的方案数，那么有转移方程
dp[i]=Cti−1pi−dti+ti−1−∑i−1j=0dp[j]∗Cti−tj−1pi−pj−d(ti−tj)+ti−tj−1 dp[i]=C_{p_i-dt_i+t_i-1}^{t_i-1}-\sum_{j=0}^{i-1}dp[j]*C_{p_i-pj-d(t_i-t_j)+t_i-t_j-1}^{t_i-t_j-1}
dp[i]=C
p
i
−dt
i
+t
i
−1
t
i
−1
−
j=0
∑
i−1
dp[j]∗C
p
i
−pj−d(t
i
−t
j
)+t
i
−t
j
−1
t
i
−t
j
−1
dp[i] dp[i]dp[i]的方案数是从0 00到pi p_ip
i
跳ti t_it
i
次的方案数减去，第j jj(0≤j<i 0\leq j<i0≤j<i)次攻击作为第一次被攻击时的方案数乘上从第j jj次攻击跳到第i ii次攻击的方案数，就是第i ii次攻击作为第一次被攻击时的方案数了。
那么最终的答案就是
ans=f[L]−∑m−1i=0dp[i]∗f[L−pi] ans=f[L]-\sum_{i=0}^{m-1}dp[i]*f[L-p_i]
ans=f[L]−
i=0
∑
m−1
dp[i]∗f[L−p
i
]
组合数预处理处理到1e7就好了但是，可能d∗ti d*t_id∗t
i
可能会爆int，都改成long long 保险一点
转自：https://blog.csdn.net/ftx456789/article/details/99306117
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll mod=1e9+7;
const int modp=998244353;
const int maxn=1e7+50;
const double eps=1e-6;
#define lowbit(x) x&(-x)
#define INF 0x3f3f3f3f
const double inf=0x7fffffff;
inline ll read()
{
ll x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
int dcmp(double x)
{
if(fabs(x)<eps)return 0;
return (x>0)?1:-1;
}
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}
ll qmod(ll a,ll b)
{
ll ans=1;
while(b)
{
if(b&1)
{
ans=(ans*a)%modp;
}
b>>=1;
a=(a*a)%modp;
}
return ans;
}
ll fac[maxn],inv[maxn];
void init(){
fac[0]=1;
for(int i=1;i<maxn;i++)
{fac[i]=fac[i-1]*i%modp;}
inv[maxn-1]=qmod(fac[maxn-1],modp-2);
for(int i=maxn-2;i>=0;i--)
{inv[i]=inv[i+1]*(i+1)%modp;}
}
ll C(ll n,ll m){
if(n<0||m<0||n<m){
return 0;
}
return fac[n]*inv[m]%modp*inv[n-m]%modp;
}
struct node{
int t,p;
}mmp[3050];
ll dp1[maxn],sum[maxn],dp2[maxn];
bool cmp(node a,node b){
return a.t<b.t;
}
int main()
{
init();
int l,d,m;
scanf("%d %d %d",&l,&d,&m);
dp1[0]=sum[0]=1;
for(int i=1;i<=l;++i){
if(i<d){
dp1[i]=0;
}
else{
dp1[i]=(sum[i-d-1]+dp1[i-d])%modp;
}
sum[i]=(sum[i-1]+dp1[i])%modp;
}
for(int i=1;i<=m;++i){
scanf("%d %d",&mmp[i].t,&mmp[i].p);
}
sort(mmp+1,mmp+1+m,cmp);
ll ans=dp1[l];
for(int i=1;i<=m;++i){
dp2[i]=C(mmp[i].p-1ll*mmp[i].t*d+mmp[i].t-1,mmp[i].t-1);
for(int j=1;j<i;++j){
dp2[i]=(dp2[i]-dp2[j]*C(mmp[i].p-mmp[j].p-1ll*d*(mmp[i].t-mmp[j].t)+mmp[i].t-mmp[j].t-1,mmp[i].t-mmp[j].t-1)%modp)%modp;
}
ans=(ans-dp2[i]*dp1[l-mmp[i].p]%modp+modp)%modp;
}
printf("%lld\n",ans);
return 0;
}