题解 微信步数

· · 题解

题解 微信步数

题目链接

假装更好的阅读体验

如果 \LaTeX 有锅请到博客内查看。

题目分析

如果将每一维度都合在一起考虑，复杂度貌似无论如何都需要带上一个 \prod_{i=1}^kw_i ，类似 CSP2020T3 的思路，如果把每一维都分开考虑可能可以降低一点复杂度。

对于维度 i 的某一个位置 p(1\le p\le w_i) ，我们可以求出一个值 \operatorname{time}_i(p) 表示在仅考虑维度 i 时小 C 走出场地需要的最少步数，如果小 C 无论如何都无法走出场地那么 \operatorname{time}_i(p)=+\infty ，求出 \operatorname{time} 这个函数之后，小 C 从 (a_1,a_2,\dots,a_k) 走出场地需要的步数就是 \min_{i=1}^k\operatorname{time}_i(a_i) 。

对于某一维度 i ，我们并不关心 \operatorname{time}_i(1\dots w_i) 这个数列所有值之间的顺序，所以我们可以给 \operatorname{time}_i(1\dots w_i) 先排个序。

我们需要求的东西是：

\sum_{1\le a_i\le w_i}\min_{i=1}^k\operatorname{time}_i(a_i)=\sum_{i\ge 1}\prod_{j=1}^k(\sum_{t=1}^{w_j}[\operatorname{time}_j(t)\ge i])

直接求出所有的 \operatorname{time}_i(j) ，然后从小到大枚举每一个 \operatorname{time}_i(j) 就可以很容易求出上面这个式子的值了，此时我们就成功地将 \prod_{i=1}^kw_i 的复杂度降为了 \sum_{i=1}^kw_i 了，按照实现不同复杂度此时可以达到 \mathcal O((\sum_{i=1}^kw_i)\log_2(\sum_{i=1}^kw_i)) 或 \mathcal O(k(\sum_{i=1}^kw_i)) 或 \mathcal O((\sum_{i=1}^kw_i)\log_2 k) ，应该可以拿到 80\rm pts 。

要拿更高的分数，需要进一步观察 \operatorname{time}_i(1\dots w_i) 这个数列的性质，可以找到两个数列 \operatorname{num}_i(1\dots p_i) 以及 \operatorname{sum}_i(1\dots s_i) 使得 \operatorname{time}_i(1\dots w_i) 是数列 \operatorname{num}_i(1\dots p_i) 和数列 \operatorname{sum}_i(1\dots s_i) 不断重复同时加上若干倍的 n 得到的：

\operatorname{num}_i(1),\dots,\operatorname{num}_i(p_i),\operatorname{sum}_i(1)+n,\dots,\operatorname{sum}_i(s_i)+n,\operatorname{sum}_i(1)+2n,\dots,\operatorname{sum}_i(s_i)+2n,\operatorname{sum}_i(1)+3n,\dots,\operatorname{sum}_i(1)+tn,\dots

并且上面这个序列是排好序的，有 \operatorname{num}_i(j)\le n,\operatorname{sum}_i(j)\le n 。

由于 \sum_{i=1}^kp_i\le n ，所以我们可以用上面的方法求出 \operatorname{num}_i() 数列这一段的值，即这个式子的值：

\sum_{i=1}^n\prod_{j=1}^k(\sum_{t=1}^{w_j}[\operatorname{time}_j(t)\ge i])

需要注意的是 \operatorname{sum}_i() 这个数列重复是一直重复到 w_i 为止的，如果把 \operatorname{sum}_i(1)+tn,\dots \operatorname{sum}_i(s_i)+tn 称作是一轮的话，那么可能最后并不能凑成一整轮，由于 \sum_{i=1}^ks_i\le n ，所以无法凑够一整轮的这一部分也可以单独算，关键是算中间重复着的若干轮。

中间重复着的若干轮数列之间的 \operatorname{sum}_i() 的大小关系都是固定的，所以我们只需要模拟第一轮其实就已经模拟了所有轮了。

假设重复的轮数为 r ，对于当前枚举的某一个 i ， c_j=\sum_{t=1}^{w_j}[\operatorname{time}_j(t)\ge i] ，那么此时造成贡献需要乘以的系数应该是这个：

\sum_{t=0}^{r-1}\prod_{j=1}^k(c_j-t\cdot s_i)=\sum_{t=0}^{r-1}\sum_{S}(-t)^{| S |}\prod_{j\in S}s_j\prod_{j\notin S}c_j=\sum_{S}\prod_{j\in S}s_j\prod_{j\not\in S}c_j(-1)^{|S|}\sum_{t=0}^{r-1}t^{|S|}

令：

f(x)=(-1)^x\sum_{t=0}^{r-1}t^x,dp(x)=\sum_{|S|=x}\prod_{j\in S}s_j\prod_{j\not\in S}c_j

那么要求的就是：

\sum_{x=0}^kf(x)dp(x)

如何求 f(x) ？自然数幂求和，设 S_k(n)=\sum_{i=0}^ni^k ：

S_k(n)=\sum_{i=0}^ni^k=\sum_{i=0}^n\sum_{j=0}^k{i\choose j}{k\brace j}j!=\sum_{j=0}^k{k\brace j}j!{n+1\choose j+1}

直接 \mathcal O(k^2) 求即可（当然可以用一些其它的方式求，这里不多说）。

如何求 dp(x) ？显然可以 dp 求，设 dp(i,x) 表示仅考虑前 i 个数的答案，那么转移就是考虑当前这个数是否包含在集合内：

dp(i,x)=dp(i-1,x)\times c_i+dp(i-1,x-1)\times s_i

最后的 dp(x)=dp(k,x) 。

如果每次都做一次 dp ，单次时间复杂度是 \mathcal O(k^2) 的，总的时间复杂度就是 \mathcal O(nk^2) 的，应该可以过，但是可以更优，不难发现这个 dp 是可撤销的，也就是我们可以删除一个数，即：

dp(i-1,x)=(dp(i,x)-dp(i-1,x-1)\times s_i)\div c_i

由于每次我们只会更改某一个位置 v ，即令 c_v\gets c_v-1 ，所以我们可以先撤销 v 造成的影响，然后更新完 c_v 后再加上 v 造成的影响，这样就不需要每次都 dp 一遍，单词时间复杂度降为 \mathcal O(k) ，总时间复杂度为 \mathcal O(nk) 。

如果算上所有操作，总时间复杂度就是 \mathcal O(k^2+n(k+\log_2w)) 的。

总感觉自己把挺简单的一个东西讲得好复杂啊。

参考代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define ch() getchar()
#define pc(x) putchar(x)
template<typename T>void read(T&x){
    static char c;static int f;
    for(c=ch(),f=1;c<'0'||c>'9';c=ch())if(c=='-')f=-f;
    for(x=0;c>='0'&&c<='9';c=ch())x=x*10+(c&15);x*=f;
}
template<typename T>void write(T x){
    static char q[64];int cnt=0;
    if(x==0)return pc('0'),void();
    if(x<0)pc('-'),x=-x;
    while(x)q[cnt++]=x%10+'0',x/=10;
    while(cnt--)pc(q[cnt]);
}
const int mod=1000000007,maxn=500006,maxk=12;
int mo(const int x){
    return x>=mod?x-mod:x;
}
int power(int a,int x){
    int re=1;
    while(x){
        if(x&1)re=1ll*re*a%mod;
        a=1ll*a*a%mod,x>>=1;
    }
    return re;
}
int cnto[maxk][maxn],cntr[maxk][maxn];
int pos[maxk],w[maxk];
int ABS(int x){
    return x<0?-x:x;
}
int num[maxk][maxn],p[maxk],pn[maxk];
int sum[maxk][maxn],s[maxk],cn[maxk];
int _s[maxk][maxk],f[maxk];
int dp[maxk];
void chkmin(int&x,int y){
    x=min(x,y);
}
int main(){
    freopen("walk.in","r",stdin);
    freopen("walk.out","w",stdout);
    int n,k;read(n),read(k);
    for(int i=1;i<=k;++i)read(w[i]);
    memset(cnto,0x3f,sizeof cnto);
    memset(cntr,0x3f,sizeof cntr);
    for(int i=1;i<=n;++i){
        int c,d;read(c),read(d);pos[c]+=d;
        if(pos[c]<0&&      -pos[c]<=w[c])chkmin(cnto[c][-pos[c]],i);
        if(pos[c]>0&&w[c]-pos[c]+1>=1   )chkmin(cntr[c][ pos[c]],i);
    }
    int ok=true,rd=0x3f3f3f3f;
    for(int i=1;i<=k;++i){
        int no=1,nr=1;
        while(cnto[i][no]<0x3f3f3f3f)++no;--no;
        while(cntr[i][nr]<0x3f3f3f3f)++nr;--nr;
        s[i]=ABS(pos[i]);
        if(no+nr>=w[i]){
            int l=1,r=w[i];
            int vl=min(cnto[i][l],cntr[i][w[i]-l+1]),
                vr=min(cnto[i][r],cntr[i][w[i]-r+1]);
            while(l<=r){
                if(vl<vr)num[i][++p[i]]=vl,++l,vl=min(cnto[i][l],cntr[i][w[i]-l+1]);
                else     num[i][++p[i]]=vr,--r,vr=min(cnto[i][r],cntr[i][w[i]-r+1]);
            }
            for(int j=1;j<=s[i];++j)
                sum[i][j]=0x3f3f3f3f;
            ok=false;rd=0;
        }
        else{
            int l=1,r=1;
            while(l<=no||r<=nr){
                if(r>nr||(l<=no&&cnto[i][l]<cntr[i][r]))
                    num[i][++p[i]]=cnto[i][l],++l;
                else
                    num[i][++p[i]]=cntr[i][r],++r;
            }
            if(pos[i]>0){
                for(int j=1;j<=s[i];++j)
                    sum[i][j]=cntr[i][nr-s[i]+j];
            }
            if(pos[i]<0){
                for(int j=1;j<=s[i];++j)
                    sum[i][j]=cnto[i][no-s[i]+j];
            }
        }
        if(s[i]>0){
            ok=false;
            rd=min(rd,(w[i]-p[i])/s[i]);
        }
    }
    if(ok)return puts("-1"),0;
    f[0]=rd;_s[0][0]=1;
    for(int i=1;i<=k;++i){
        _s[i][0]=0;
        for(int j=1;j<=i;++j)
            _s[i][j]=mo(_s[i-1][j-1]+mo(mod-1ll*(i-1)*_s[i-1][j]%mod));
        f[i]=1;int tp=false;
        for(int j=0;j<=i;++j){
            if((rd-j)%(i+1)==0&&!tp)
                f[i]=1ll*f[i]*((rd-j)/(i+1))%mod,tp=true;
            else
                f[i]=1ll*f[i]*(rd-j)%mod;
        }
        for(int j=0;j<i;++j)
            f[i]=mo(f[i]+mo(mod-1ll*f[j]*_s[i][j]%mod));
    }
    for(int i=1;i<=k;i+=2)
        f[i]=mo(mod-f[i]);
    int ans=0;
    int all=1;
    for(int i=1;i<=k;++i)
        all=1ll*all*w[i]%mod;
    int pre=0;
    while("Imakf ak ioi"){
        int mn=0x3f3f3f3f,mp=0;
        for(int i=1;i<=k;++i)
            if(pn[i]<p[i]&&num[i][pn[i]+1]<mn)
                mn=num[mp=i][pn[i]+1];
        if(!all||mn>=0x3f3f3f3f){
            ans=mo(ans+1ll*(n-pre)*all%mod);
            pre=n;break;
        }
        ans=mo(ans+1ll*(mn-pre)*all%mod);
        all=1ll*all*power(w[mp]-pn[mp],mod-2)%mod;
        ++pn[mp];all=1ll*all*(w[mp]-pn[mp])%mod;
        pre=mn;
    }
    dp[0]=1;
    for(int i=1;i<=k;++i){
        cn[i]=w[i]-p[i];pn[i]=0;
        for(int j=i;j>=1;--j)
            dp[j]=mo(1ll*dp[j]*s[i]%mod+1ll*dp[j-1]*cn[i]%mod);
        dp[0]=1ll*dp[0]*s[i]%mod;
    }
    pre=0;
    while("Imakf ak ioi"){
        int mn=0x3f3f3f3f,mp=0;
        for(int i=1;i<=k;++i)
            if(pn[i]<s[i]&&sum[i][pn[i]+1]<mn)
                mn=sum[mp=i][pn[i]+1];
        int add=0;
        for(int i=0;i<=k;++i)
            add=mo(add+1ll*dp[i]*f[k-i]%mod);
        if(mn>=0x3f3f3f3f){
            ans=mo(ans+1ll*(n-pre)*add%mod);
            pre=n;break;
        }
        ans=mo(ans+1ll*(mn-pre)*add%mod);
        ++pn[mp];int I=power(cn[mp],mod-2);
        for(int i=k;i>=1;--i)
            dp[i]=1ll*mo(mod-1ll*dp[i+1]*s[mp]%mod+dp[i])*I%mod;
        --cn[mp];
        for(int i=1;i<=k;++i)
            dp[i]=mo(1ll*dp[i]*cn[mp]%mod+1ll*dp[i+1]*s[mp]%mod);
        pre=mn;
    }
    all=1;
    for(int i=1;i<=k;++i){
        w[i]-=(p[i]+rd*s[i]);
        all=1ll*all*w[i]%mod;
        if(s[i]&&w[i]<=s[i])
            s[i]=w[i];
        pn[i]=0;
    }
    pre=0;
    while("Imakf ak ioi"){
        int mn=0x3f3f3f3f,mp=0;
        for(int i=1;i<=k;++i)
            if(pn[i]<s[i]&&sum[i][pn[i]+1]<mn) 
                mn=sum[mp=i][pn[i]+1];
        if(!all||mn>=0x3f3f3f3f)break;
        ans=mo(ans+1ll*(mn-pre)*all%mod);//puts("ok");
        all=1ll*all*power(w[mp]-pn[mp],mod-2)%mod;
        ++pn[mp];all=1ll*all*(w[mp]-pn[mp])%mod;
        pre=mn;
    }
    write(ans),pc('\n');
    return 0;
}