先判定无解，当且仅当存在一个位置使得移动$n$步后没有结束且仍在原地
暴力枚举移动的步数，记$S_{i}$为移动$i$步（后）未离开范围的点个数，则恰好移动$i$步的人数为$S_{i-1}-S_{i}$（特别的$S_{0}=P$），答案即为$sum_{i=1}^{D}(S_{i-1}-S_{i})i=sum_{i=0}^{D-1}S_{i}$（其中$D=min_{S_{i}=0}i$）
考虑如何求出$S_{i}$，记$len_{j}$为第$j$维的合法范围，由于每一维互不干扰，则有$S_{i}=prod_{j=1}^{m}len_{j}$
由于每$n$步必然重复向一个方向移动，那么$Dle nmax w_{i}$，总复杂度即$o(nmmax w_{i})$
进一步优化，将$S_{i}$按$i mod n$的值分组，对于第$i$组（$iin [0,n)$），$i$单独计算，然后求出$i+n$时的$len_{j}$，记$n$步的总位移为$d_{i}$，则第$kn+i(kge 1)$步时$len'_{j}=max(len_{j}-(k-1)|d_{j}|,0)$
写成式子，即$sum_{k=1}^{D'}prod_{j=1}^{m}(len_{j}+|d_{j}|-k|d_{j}|)$（其中$D'=min_{j=1}^{m}frac{len_{j}}{|d_{j}|}$，因为$max$取0后一定为0，不需要再计算）
将后式$o(m^{2})$暴力展开，那么就是一个关于$k$的一个$m+1$次多项式，多项式的前缀和也可以$o(m^{2})$计算，总复杂度即为$o(nm^{2})$
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 500005 4 #define M 20 5 #define mod 1000000007 6 int n,m,ans,w[M],x[N],y[N],d[M],mx[N<<1][M],mn[N<<1][M],g[M],sum[M][M]; 7 int ksm(int n,int m){ 8 if (!m)return 1; 9 int s=ksm(n,m>>1); 10 s=1LL*s*s%mod; 11 if (m&1)s=1LL*s*n%mod; 12 return s; 13 } 14 int mul(int x,int y){ 15 for(int i=m+1;i;i--)g[i]=(1LL*g[i-1]*x+1LL*g[i]*y)%mod; 16 g[0]=1LL*g[0]*y%mod; 17 } 18 int calc(int k,int x){ 19 int s=1,ans=0; 20 for(int i=0;i<=k+1;i++){ 21 ans=(ans+1LL*s*sum[k][i])%mod; 22 s=1LL*s*x%mod; 23 } 24 return ans; 25 } 26 int main(){ 27 scanf("%d%d",&n,&m); 28 sum[0][1]=1; 29 for(int i=1;i<=m;i++){//i+1次多项式， 30 int y=0; 31 for(int x=0;x<=i+1;x++){ 32 y=(y+ksm(x,i))%mod; 33 memset(g,0,sizeof(g)); 34 g[0]=y; 35 for(int j=0;j<=i+1;j++) 36 if (j!=x){ 37 mul(1,mod-j); 38 mul(0,ksm((x-j+mod)%mod,mod-2)); 39 } 40 for(int j=0;j<=i+1;j++)sum[i][j]=(sum[i][j]+g[j])%mod; 41 } 42 } 43 for(int i=1;i<=m;i++)scanf("%d",&w[i]); 44 for(int i=1;i<=n;i++){ 45 scanf("%d%d",&x[i],&y[i]); 46 d[x[i]]+=y[i]; 47 for(int j=1;j<=m;j++){ 48 mx[i][j]=max(mx[i-1][j],d[j]); 49 mn[i][j]=min(mn[i-1][j],d[j]); 50 } 51 } 52 for(int i=n+1;i<=2*n;i++){ 53 d[x[i-n]]+=y[i-n]; 54 for(int j=1;j<=m;j++){ 55 mx[i][j]=max(mx[i-1][j],d[j]); 56 mn[i][j]=min(mn[i-1][j],d[j]); 57 } 58 } 59 for(int i=1;i<=m;i++)d[i]/=2; 60 bool flag1=0,flag2=0; 61 for(int i=1;i<=m;i++) 62 if (d[i])flag1=1; 63 for(int i=1;i<=m;i++) 64 if (mx[n][i]-mn[n][i]>w[i])flag2=1; 65 //flag1说明离开了原位置，flag2说明一定是一轮 66 if ((!flag1)&&(!flag2)){ 67 printf("-1"); 68 return 0; 69 } 70 for(int i=0;i<n;i++){ 71 int s=1; 72 for(int j=1;j<=m;j++)s=1LL*s*max(w[j]-(mx[i][j]-mn[i][j]),0)%mod; 73 ans=(ans+s)%mod; 74 } 75 for(int i=n;i<2*n;i++){ 76 bool flag=0; 77 for(int j=1;j<=m;j++) 78 if (w[j]-(mx[i][j]-mn[i][j])<0)flag=1; 79 if (flag)break; 80 memset(g,0,sizeof(g)); 81 g[0]=1; 82 for(int j=1;j<=m;j++)mul(mod-abs(d[j]),w[j]-(mx[i][j]-mn[i][j])+abs(d[j])); 83 int D=0x3f3f3f3f; 84 for(int j=1;j<=m;j++) 85 if (d[j])D=min(D,(w[j]-(mx[i][j]-mn[i][j]))/abs(d[j])+1); 86 for(int j=0;j<=m;j++)ans=(ans+1LL*g[j]*calc(j,D))%mod; 87 } 88 printf("%d",ans); 89 }