本文将同步发布于：
题目
题目描述
小 R 最近在玩一款游戏。在游戏中，小 R 要依次打 \(n\) 个怪兽，他需要打败至少 \(k\) 个怪兽才能通关。小 R 有两个属性值，分别是攻击力 \(A\) 和耐力 \(R\)，每个怪兽也有两个属性值，分别是防御力 \(D\) 和生命值 \(H\)（不同的怪兽属性值可能不同）。小 R 每攻击一次怪兽，可以让怪兽的生命值减少 \(\max(A-D,1)\)点，同时小 R 的耐力会减少 \(1\)。怪兽不会攻击。若在一次攻击之后，怪兽的生命值 \(\leq 0\)，则小 R 胜利。若在一次攻击之后，在怪兽的生命值大于 \(0\) 的条件下，小 \(R\) 的耐力值降低到了 \(0\)，则怪兽胜利。在和一个怪兽战斗结束后，无论输赢，小 R 都会恢复全部的耐力值。
现在，小 R 的攻击 \(A\) 和每个怪兽的防御力 \(D\) 是确定的，小 R 的耐力值 \(R\) 是一个在 \([1,m]\) 区间内的整数，第 \(i\) 个怪兽的生命值是一个在 \([X_i,Y_i]\) 区间内的整数。求有多少种情况使得小 R 能通关，你只需要输出答案模 \(10^9+7\) 的值就可以了。
两种情况不同当且仅当这两种情况下小 R 的耐力值不同或者其中一个怪兽的生命值不同。
\(1\leq k\leq n\leq 50\)，\(1\leq m,A,D_i\leq 10^9\)。
题解
简单暴力
考虑枚举耐力值 \(R\in [1,m]\)，那么我们可以轻松得到一个关于方案数的动态规划：
即 \(d_i=\max(A-D_i,1)\)。
设 \(f_{i,j}\) 表示考虑前 \(i\) 个怪兽，打败恰好 \(j\) 个的方案数，我们不难得到转移。
\[\begin{cases}
f_{i-1,j-1}(Y_i-X_i+1)&\to f_{i,j},Rd_i\geq Y_i\\
f_{i-1,j}(Y_i-X_i+1)&\to f_{i,j},Rd_i<X_i\\
f_{i-1,j-1}(Rd_i-X_i+1)&\to f_{i,j},X_i\leq Rd_i<Y_i\\
f_{i-1,j}(Y_i-Rd_i)&\to f_{i,j},X_i\leq Rd_i<Y_i\\
\end{cases}
\]
这个算法的时间复杂度为 \(\Theta(n^2m)\)。
多项式
我们把 \(f_i\) 看作一个多项式，\(f_{i,j}\) 为 \(x^j\) 的系数。
那么上面的转移方程可以看作 \(f_i=f_{i-1}\times (ax+b)\)。
最后的结果就是对 \(x^k,x^{k+1},\cdots,x^n\) 的系数求和。
拉格朗日插值
考虑到上述式子可以表示为一个关于 \(R\) 的 \(n\) 次多项式，那么我们不妨用拉格朗日插值求出 \(n+2\) 个点值，求出前缀和的多项式表示，然后做差求解。
求出这个函数的分段点，插值即可。
参考程序
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
static char buf[1<<21],*p1=buf,*p2=buf;
inline int read(void){
reg char ch=getchar();
reg int res=0;
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) res=10*res+(ch^'0'),ch=getchar();
return res;
}inline int max(reg int a,reg int b){
return a>b?a:b;
}inline int min(reg int a,reg int b){
return a<b?a:b;
}const int MAXN=50+5;
const int mod=1e9+7;struct modInt{
int x;
inline modInt(reg int x=0):x(x){
x=(x%mod+mod)%mod;
assert(0<=x&&x<mod);
return;
}
inline modInt operator+(const modInt& a)const{
reg int sum=x+a.x;
return sum>=mod?sum-mod:sum;
}
inline modInt operator-(const modInt& a)const{
reg int sum=x-a.x;
return sum<0?sum+mod:sum;
}
inline modInt operator*(const modInt& a)const{
return 1ll*x*a.x%mod;
}
inline void operator+=(const modInt& a){
x+=a.x;
if(x>=mod) x-=mod;
return;
}
inline void operator-=(const modInt& a){
x-=a.x;
if(x<0) x+=mod;
return;
}
inline void operator*=(const modInt& a){
x=1ll*x*a.x%mod;
return;
}
};inline modInt fpow(modInt x,reg int exp){
modInt res=1;
while(exp){
if(exp&1)
res*=x;
x*=x,exp>>=1;
}
return res;
}inline modInt operator/(const modInt& a,const modInt& b){
return a*fpow(b,mod-2);
}inline void operator/=(modInt& a,const modInt& b){
a*=fpow(b,mod-2);
return;
}struct Node{
int delta,l,r;
};int n,m,k,A;
Node a[MAXN];
modInt f[MAXN][MAXN];inline modInt getVal(reg int R){
for(reg int i=0;i<=n;++i)
for(reg int j=0;j<=i;++j)
f[i][j]=0;
f[0][0]=1;
for(reg int i=0;i<n;++i){
for(reg int j=0;j<=i;++j)
if(f[i][j].x){
reg ll val=1ll*a[i+1].delta*R;
if(val>=a[i+1].r)
f[i+1][j+1]+=f[i][j]*(a[i+1].r-a[i+1].l+1);
//(len) x
else if(val<a[i+1].l)
f[i+1][j]+=f[i][j]*(a[i+1].r-a[i+1].l+1);
//(len)
else{
f[i+1][j]+=f[i][j]*(a[i+1].r-val);
f[i+1][j+1]+=f[i][j]*(val-a[i+1].l+1);
//(rig)+(lef)*x
}
}
}
modInt res=0;
for(reg int i=k;i<=n;++i)
res+=f[n][i];
return res;
}int B;inline modInt Lagrange(reg int lef,reg int rig,modInt x[],modInt y[],reg int X){
modInt res=0;
for(reg int i=lef;i<=rig;++i){
modInt pod=1;
for(reg int j=lef;j<=rig;++j)
if(i!=j)
pod*=(modInt(X)-x[j])/(x[i]-x[j]);
res+=y[i]*pod;
}
return res;
}inline modInt getAns(reg int lef,reg int rig){
if(rig-lef+1<=B){
modInt res=0;
for(reg int i=lef;i<=rig;++i)
res+=getVal(i);
return res;
}
else{
modInt x[B],y[B];
for(reg int i=0;i<B;++i)
x[i]=lef+i,y[i]=getVal(lef+i);
for(reg int i=1;i<B;++i)
y[i]+=y[i-1];
return Lagrange(0,B-1,x,y,rig)-Lagrange(0,B-1,x,y,lef-1);
}
}int main(void){
n=read(),m=read(),k=read(),A=read();
B=n+2;
for(reg int i=1;i<=n;++i){
static int d,x,y;
d=read(),x=read(),y=read();
a[i].delta=max(A-d,1),a[i].l=x,a[i].r=y;
}
vector<int> V;
V.push_back(1),V.push_back(m+1);
for(reg int i=1;i<=n;++i){
V.push_back((a[i].l+a[i].delta-1)/a[i].delta);
V.push_back(a[i].r/a[i].delta+1);
}
sort(V.begin(),V.end()),V.erase(unique(V.begin(),V.end()),V.end());
while(V.back()>m+1) V.pop_back();
modInt ans=0;
for(reg int i=1,siz=V.size();i<siz;++i)
ans+=getAns(V[i-1],V[i]-1);
printf("%d\n",ans.x);
return 0;
}
