题解 微信步数
xiaolilsq
2020-12-24 22:10:12
# 题解 微信步数
[题目链接](https://www.luogu.com.cn/problem/P7116)
[假装更好的阅读体验](https://www.cnblogs.com/lsq147/p/14186642.html)
如果 $\LaTeX$ 有锅请到博客内查看。
## 题目分析
如果将每一维度都合在一起考虑，复杂度貌似无论如何都需要带上一个 $\prod_{i=1}^kw_i$ ，类似 [CSP2020T3](https://www.luogu.com.cn/problem/P7077) 的思路，如果把每一维都分开考虑可能可以降低一点复杂度。
对于维度 $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))$ 的。
~~总感觉自己把挺简单的一个东西讲得好复杂啊。~~
## 参考代码
```cpp
#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;
}
```