微信步数

题解

现在才补一年前的题。

首先我们的考虑一个简单的暴力。然而我考场上连这个暴力都没想到
我们将一个点能走多少步转化一下，通过整体来看。
我们考虑走了这一步后还有多少点能够幸存，即没有走出整个网格。
显然，每一维在幸存的长度上是独立的，如果第$i$维我们幸存的长度为$le{n}_i$，那么我们总的幸存的的格子数是${\prod }_{i=1}^{k}le{n}_i$。显然所有幸存的所有点是连续的多面体，我们可以把它们乘起来得到总答案。
我们考虑对于这一维，我们幸存的区间是$[L_i,R_i]$，那么我们的移动相当于让我们的区间变成$[L_i+x,R_i+x]$。
如果这次移动后有部分区间超出我们$[1,w_i]$的限制了，那么这一部分区间显然是应当被删去的，那么幸存的区间就变成了$[\max (1,L_i+x),\min (w_i,R_i+x)]$。
我们新的$le{n}_i$就成了$\min (w_i,R_i+x)-\max (1,L_i+x)+1$。
这样，我们只需要每次操作更改我们的操作这一维的长度即可。
显然这样暴力的时间复杂度是$O\left(n\max (w_i)\right)$的，大概可以拿$30pts$。

但显然上述过程是可以优化的。
我们的第一轮操作由于最开始是没有模板的，所以第一轮的移动是与其它轮移动是没有规律的，我们记在第一轮第$i$维移动带来的变化后的长度为$a_i$。
之后每一轮带来的变化都是固定的，我们记其使我们长度的变化为$b_i$。
显然，之后的第$i+1$轮移动后，我们的第$j$维还剩的长度为$a_j-i{b}_j$。
我们不如再记录一下第$2$轮之后每一轮的前$i$步能对我们的第$j$维产生影响的大小为$f_{i,j}$。
这样，我们就可以知道我们第$i$轮第$j$次的大小了。
我们假设总共进行了$T+2$轮，那么从第$2$轮开始的贡献为，
$$\sum _{x=0}^T\sum _{i=1}^n\prod _{j=1}^k(a_j-x{b}_j-f_{i,j})=\sum _{i=1}^n\sum _{x=0}^T\prod _{j=1}^k(a_j-x{b}_j-f_{i,j})$$
这时我们可以把后面的${\prod }_{j=1}^k(a_j-x{b}_j-f_{i,j})$看成一个关于$x$的$k$次多项式，对于所有的$i\in [0,k]$，求出它的系数，将它乘上${\sum }_{x=0}^T{x}^i$。
前面的系数显然可以通过$O\left(k^2\right)$的背包求出，直接暴力多项式乘就行了。
后面的${\sum }_{x=0}^T{x}^i$，$T$显然是${\min }_{j=1}^k\lceil \frac{a_j-f_{i,j}}{b_j}-1\rceil$，而${\sum }_{x=0}^T{x}^i$我们可以用斯特林反演求出。
由于$n^m={\sum }_{k=0}^m\left\{\genfrac{}{}{0ex}{}{m}{k}\right\}{n}^{\underline{k}}$，
所以有
$$\sum _{x=0}^T{x}^i=\sum _{x=0}^T\sum _{k=0}^i\left\{\genfrac{}{}{0ex}{}{i}{k}\right\}{x}^{\underline{k}}=\sum _{k=0}^i\left\{\genfrac{}{}{0ex}{}{i}{k}\right\}\sum _{x=0}^T{x}^{\underline{k}}=\sum _{k=0}^i\left\{\genfrac{}{}{0ex}{}{i}{k}\right\}k!\sum _{x=0}^T\left(\genfrac{}{}{0ex}{}{x}{k}\right)=\sum _{k=0}^i\left\{\genfrac{}{}{0ex}{}{i}{k}\right\}k!\left(\genfrac{}{}{0ex}{}{T+1}{k+1}\right)$$
显然，这东西是可以$O\left(k\right)$求出的 ，很经典的式子。
我们要对于每个$i\in [0,k]$都要算一个右边的式子，显然这部分也是$O\left(k^2\right)$的。

所以这样做的话时间复杂度是$O\left(n{k}^2\right)$的，已经可以过了。
但我们仍然是可以继续优化的，前面的${\prod }_{j=1}^k(a_j-x{b}_j-f_{i,j})$是可以通过分治$NTT$或者$MTT$或者$karatsuba$乘法求出来的。
而后面的${\sum }_{x=0}^T{x}^i$由于$T$的取值只会有两个，是可以预处理的。
所以时间复杂度就变为了$O\left(nk{\log }^{2}kornk\sqrt{k}\right)$了 ，虽然我觉得没有人会这样打。

源码

#include<bits/stdc++.h>
using namespace std;
#define MAXN 500005
#define lowbit(x) (x&-x)
#define reg register
#define pb push_back
#define mkpr make_pair
#define fir first
#define sec second
#define lson (rt<<1)
#define rson (rt<<1|1)
typedef long long LL;
typedef unsigned long long uLL;       
const int INF=0x3f3f3f3f;       
const int mo=1e9+7;
const int inv2=499122177;
const int jzm=2333;
const int zero=10000;
const int orG=3,invG=332748118;
const double Pi=acos(-1.0);
const double eps=1e-5;
typedef pair<LL,int> pii;
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}
template<typename _T>
void read(_T &x){_T f=1;x=0;char s=getchar();while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}x*=f;
}
template<typename _T>
void print(_T x){if(x<0){x=(~x)+1;putchar('-');}if(x>9)print(x/10);putchar(x%10+'0');}
int gcd(int a,int b){return !b?a:gcd(b,a%b);}
int add(int x,int y,int p){return x+y<p?x+y:x+y-p;}
void Add(int &x,int y,int p){x=add(x,y,p);}
int n,k,a[15],b[15],w[15],l[15],r[15],f[MAXN][15],c[MAXN],d[MAXN],ans,dp[15];
int fac[MAXN],ff[MAXN],S[15][15];
void init(){fac[0]=fac[1]=ff[1]=1;for(int i=2;i<=k+1;i++)fac[i]=1ll*i*fac[i-1]%mo,ff[i]=1ll*(mo-mo/i)*ff[mo%i]%mo;S[0][0]=1;for(int i=1;i<=k;i++)for(int j=1;j<=k;j++)S[i][j]=add(S[i-1][j-1],1ll*j*S[i-1][j]%mo,mo);
}
signed main(){read(n);read(k);ans=1;init();for(int i=1;i<=k;i++)read(w[i]),l[i]=1,r[i]=w[i],ans=1ll*ans*w[i]%mo;for(int i=1;i<=n;i++){read(c[i]);read(d[i]);l[c[i]]+=d[i];r[c[i]]+=d[i];l[c[i]]=max(l[c[i]],1);r[c[i]]=min(r[c[i]],w[c[i]]);int summ=1;for(int j=1;j<=k;j++)summ=1ll*summ*(r[j]-l[j]+1)%mo;ans=add(summ,ans,mo);if(l[c[i]]>r[c[i]]){printf("%d\n",ans);return 0;}}for(int i=1;i<=k;i++)a[i]=r[i]-l[i]+1;int sum=0;for(int i=1;i<=n;i++){l[c[i]]+=d[i];r[c[i]]+=d[i];l[c[i]]=max(l[c[i]],1);r[c[i]]=min(r[c[i]],w[c[i]]);int summ=1;for(int j=1;j<=k;j++)summ=1ll*summ*(r[j]-l[j]+1)%mo;sum=add(summ,sum,mo);if(l[c[i]]>r[c[i]]){printf("%d\n",add(sum,ans,mo));return 0;}for(int j=1;j<=k;j++)f[i][j]=a[j]-(r[j]-l[j]+1);}for(int i=1;i<=k;i++)b[i]=f[n][i];bool flag=0;for(int i=1;i<=k;i++)flag|=(b[i]!=0);if(!flag){puts("-1");return 0;} for(int i=1;i<=n;i++){for(int j=1;j<=k;j++)dp[j]=0;dp[0]=1;for(int j=1;j<=k;j++){for(int k=j;k>0;k--)dp[k]=add(1ll*(a[j]-f[i][j])*dp[k]%mo,1ll*(mo-b[j])*dp[k-1]%mo,mo);dp[0]=1ll*(a[j]-f[i][j])*dp[0]%mo;		}int T=INF;for(int j=1;j<=k;j++)if(b[j])T=min(T,(a[j]-f[i][j])/b[j]);for(int j=0;j<=k;j++){int tmp=1,num=0;for(int l=0;l<=k;l++)tmp=1ll*(T+1-l)*ff[l+1]%mo*tmp%mo,Add(num,1ll*S[j][l]*fac[l]%mo*tmp%mo,mo);Add(ans,1ll*num*dp[j]%mo,mo);}}printf("%d\n",ans);return 0;
}

谢谢！！！