「题解」小 R 打怪兽 monster

本文将同步发布于：

洛谷博客；
csdn；
博客园；
简书。

题目

题目描述

小 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;
}

Lu_Anlai