P7116 [NOIP2020] 微信步数 解法

· · 题解

本文同步发布于博客园

题目链接

题意

大体就是说在一个 k 维空间按某一运动轨迹在不同点开始走，走出边界就停止那一天。求一共走了多少步。

做法

转换

直接去算每一个点能走多远不好算，我们先转换一下，题目其实是等同于在某一轨迹中，能有多少个点当起点。（类似将原本要竖着切的正方形蛋糕横着切了，其实是等价的）

计算

然后就是计算了，我们考虑每一步的起点。

我们将其拆解为第一个周期与后续周期。（因为画图我们可以发现第一周期的变化是特殊的而往后的周期变化是规律的）

我们可以根据每一轨迹的每一维运动幅度来算出这一维还能当起点的数。

ll ans=0;
for(int i=0;i<=n;i++){
    ll s=1;//在第i步后还有多少符合条件的起点 
    for(int j=1;j<=m;j++)s=s*max(0,(w[j]-(r[i][j]-l[i][j])))%mod;
    ans=(ans+s)%mod;
}

这就是第一周期的步数了。

至于往后的周期，我们需要得到新失去的起点，所以我们需要将其归一，其中 e_j 为第 j 维的净位移。

for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++){
        r[i][j]=max(0,r[i][j]+e[j]-r[n][j]);//偏移量 
        l[i][j]=min(0,l[i][j]+e[j]-l[n][j]);
    }

我们还需要每一维的波动幅度。

for(int j=1;j<=m;j++)b[j]=r[n][j]-l[n][j];//波动幅度

接下来就是式子化简了

假设我们知道每一维的这一步剩下的起点数量为 x，每一周期会减少 b，显然能进行的区间数就是 T = \min\limits_{j: b_j>0} \lfloor x_j / b_j\rfloor。

那么，贡献就是：

\sum_{t=0}^{T} \prod_{j=1}^m (x_j - t\cdot b_j)

考虑如何高效计算（毕竟 T 的范围可不小），将其展开，其中 c_j 为待定系数：

P(t) = \prod_{j=1}^m (x_j - b_j·t) = \sum_{j=0}^m \left(c_j·t^j\right) \sum_{t=0}^T P(t) = c_0·(T+1) + \sum_{j=1}^k \left(c_j·\sum_{t=1}^T t^j\right)

这是一个有关 t 的多项式。

怎么计算 c_j？多项式乘法！

初始 c_0=1，然后每次乘以 x_j-b_jz 其中 z 为形式变量。

for(int j=0;j<=m;j++)f[0][j]=0;
f[0][0]=1;
int t=inf;
for(int j=1;j<=m;j++){
    int x=a[j]-r[i][j]+l[i][j];//还活着这么多 
    if(x<=0)goto M1;//一个容易错的语法，这里是某个维度已经无法容纳了，直接退出 
    if(b[j]>0)t=min(t,x/b[j]);//可以走的轮数 
    for(int k=0;k<=m;k++){//这里是多项式乘法 ,计算有关轮数t的函数的系数 
        f[j][k]=f[j-1][k]*x%mod;
        if(k>0)f[j][k]=(f[j][k]+f[j-1][k-1]*(-b[j]))%mod;//每轮会少b[j]个 
    }
}

我们还有一个棘手的没算呢!

\sum_{t=1}^T t^j

这里要用一个高级的东西了：拉格朗日插值 - qAlex_Weiq。

拉插简单说就是对于 n 的 m+1 次多项式，我们只要知道其在 m+2 上的点值，就可以唯一确定这个多项式

这里就不详细讲了，直接给出公式：

其中，\displaystyle S_m(n)=\sum_{i=1}^n i^m，我们选取最简单的点：x_i=i（i=1,2,\dots,m+2），对应的 y_i=S_m(i)。

\ell_i(n)=\prod_{\substack{j=1\\j\neq i}}^{m+2}\frac{n-j}{i-j}.

每一项：y_i \cdot t \cdot (n-i)^{-1} \cdot [(i-1)! (m+2-i)!]^{-1} \cdot (-1)^{i-m-2}

暴力求 O(m^2)，预处理分子可以做到 O(m)。

ll calc(ll n,ll m){//求1^m+2^m+3^m+...+n^m，拉格朗日插值 
    ll res=0;
    if(n<=m+2){//n小，直接算 
        for(int i=1;i<=n;i++)res=(res+ksm(i,m))%mod;
    }else{
        fac[0]=1;
        for(int i=1;i<=m+1;i++)fac[i]=fac[i-1]*i%mod;
        ll t=1;
        for(int i=1;i<=m+2;i++)t=t*(n-i)%mod;//分子 
        ll y=0;//点值 y_i 
        int fg=(m+2)%2?1:-1;
        for(int i=1;i<=m+2;i++){
            y=(y+ksm(i,m))%mod;
            res+=fg*y*t%mod*ksm(n-i,mod-2)%mod*ksm(fac[i-1]*fac[m+2-i]%mod,mod-2);
            fg=-fg;
        }
        res=(res%mod+mod)%mod;
    }
    return res;
}

这样，整道题就差不多了。

代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
inline int rd(){
    int x=0,id=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')id=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*id;
}
const int inf=0x3f3f3f3f,N=5e5+3,mod=1e9+7;
ll ksm(ll a,ll b){
    ll res=1;
    for(a%=mod;b;b>>=1,a=a*a%mod)if(b&1)res=res*a%mod;
    return res;
}
ll fac[N];
ll calc(ll n,ll m){//求1^m+2^m+3^m+...+n^m，拉格朗日插值 
    ll res=0;
    if(n<=m+2){//n小，直接算 
        for(int i=1;i<=n;i++)res=(res+ksm(i,m))%mod;
    }else{
        fac[0]=1;
        for(int i=1;i<=m+1;i++)fac[i]=fac[i-1]*i%mod;
        ll t=1;
        for(int i=1;i<=m+2;i++)t=t*(n-i)%mod;//分子 
        ll y=0;//点值 y_i 
        int fg=(m+2)%2?1:-1;
        for(int i=1;i<=m+2;i++){
            y=(y+ksm(i,m))%mod;
            res+=fg*y*t%mod*ksm(n-i,mod-2)%mod*ksm(fac[i-1]*fac[m+2-i]%mod,mod-2);
            fg=-fg;
        }
        res=(res%mod+mod)%mod;
    }
    return res;
}
int w[20],e[20],l[N][20],r[N][20];
int a[20],b[20],h[20];
ll f[20][20];
int c[N],d[N];
int n,m;
int main(){
    n=rd(),m=rd();
    for(int i=1;i<=m;i++)w[i]=rd();
    for(int i=1;i<=n;i++){
        c[i]=rd(),d[i]=rd();
        e[c[i]]+=d[i];
        for(int j=1;j<=m;j++)l[i][j]=l[i-1][j],r[i][j]=r[i-1][j];
        l[i][c[i]]=min(l[i][c[i]],e[c[i]]);
        r[i][c[i]]=max(r[i][c[i]],e[c[i]]);//一个安全区间，或者是会经过的距离 
    }
    bool ls=1;
    for(int i=1;i<=m;i++)if(e[i]!=0||r[n][i]-l[n][i]>=w[i])ls=0;//不会兜圈子 
    if(ls)return puts("-1"),0;
    for(int j=1;j<=m;j++)a[j]=w[j]-(r[n][j]-l[n][j]);//可移动格子 
    ll ans=0;
    for(int i=0;i<=n;i++){
        ll s=1;//在第i步后还有多少符合条件的起点 
        for(int j=1;j<=m;j++)s=s*max(0,(w[j]-(r[i][j]-l[i][j])))%mod;
        ans=(ans+s)%mod;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            r[i][j]=max(0,r[i][j]+e[j]-r[n][j]);//偏移量 
            l[i][j]=min(0,l[i][j]+e[j]-l[n][j]);
        }
    for(int j=1;j<=m;j++)b[j]=r[n][j]-l[n][j];//波动幅度 
    int lst=-1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++)f[0][j]=0;
        f[0][0]=1;
        int t=inf;
        for(int j=1;j<=m;j++){
            int x=a[j]-r[i][j]+l[i][j];//还活着这么多 
            if(x<=0)goto M1;//一个容易错的语法，这里是某个维度已经无法容纳了，直接退出 
            if(b[j]>0)t=min(t,x/b[j]);//可以走的轮数 
            for(int k=0;k<=m;k++){//这里是多项式乘法 ,计算有关轮数t的函数的系数 
                f[j][k]=f[j-1][k]*x%mod;
                if(k>0)f[j][k]=(f[j][k]+f[j-1][k-1]*(-b[j]))%mod;//每轮会少b[j]个 
            }
        }
        ans+=f[m][0]*(t+1)%mod;//常数项 
        if(t!=lst){
            lst=t;
            for(int j=1;j<=m;j++)h[j]=calc(t,j);
        }
        for(int j=1;j<=m;j++)ans+=h[j]*f[m][j]%mod;//每一时刻的答案 
    }
    M1:;//有个冒号 
    ans=(ans%mod+mod)%mod;
    cout<<ans<<"\n";
    return 0;
}