[补]NOIP2020T4微信步数

Posted on Edited on In

[补]NOIP2020T4微信步数

题意：一个人在 \(k\) 维平面上，每一维范围是 \([1,W_i]\) 上的任意一个位置，初始可以在任何一个位置

这个人在空间上游走，每 \(n\) 步为一轮不断重复，每一步是一个方向上走-1或者1，求所有情况下 最后他离开空间范围的时间 之和

分析：

行走是循环的，每一维可以先看做独立，然后离开范围的时间就是每一维取 \(\min\)

一个简单的思路：

求出每一维每一个位置离开的时间，然后 \(k\) 路归并得到答案，复杂度为 \(O((\sum W_i)k+nk)\)

容易想到根据循环来优化计算，但是如果以每一个位置为元素进行考虑，难以处理不同长度循环之间的合并

\[ \ \]

更换思路：

简单的计数方法的转换：

从初始位置离开的时间之和 = 前 \(i(i\ge 0)\) 步还未离开空间的初始位置个数之和

令 \(F_{i,j}\) 为 \(i\) 这一维 \(j\) 步还未离开的初始位置个数，则答案就是 \(\begin{aligned} \sum_{i\ge 0}\prod F_{i,j}\end{aligned}\)

此时观察发现除了第一轮需要特殊考虑以外，其它的 \(F_{i,j}\) 可以表示为 \(\max\lbrace0,F_{i,j-n}-D_i\rbrace\) (其中 \(D_i\) 为每一轮 \(i\) 这一维偏移的量)

对于前面 \(n\) (好像是 \(2n\) )个特殊考虑，后面对于每一个不同的 \(i\mod n\) 可以放在一起考虑，用一个统一的式子表示

然后计算就是类似 \(\begin{aligned} \sum_{i\ge 0}\prod (G_j-i D_j)\end{aligned}\) ，以 \(i\) 为元，所求的就是是一个 \(k\) 次多项式前缀和，也就是一个 \(k+1\) 次多项式的点值

暴力的方法就是 求出前面 \(k+2\) 项的值，然后用 拉格朗日插值/高斯消元 得到答案，复杂度为 \(O(nk^2-nk^3)\) (如果插值写好一点，复杂度主要受限于求值)

~~然后甚至可以无脑吸多项式做到 \(O(nk\log ^2k)\) ~~

求值时可以发现 对于 \(i\) 所求的 \(j\) 处点值的积式里面 最多只有一项和 \(i-1\) 不同，因而可以特殊考虑以优化求值复杂度

下面是 \(nk^2\) ，由于求值已经是 \(k^2\) 了，所以插值也没优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
char IO;
int rd(){
	int s=0,f=0;
	while(!isdigit(IO=getchar())) if(IO=='-') f=1;
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int N=5e5+10,P=1e9+7;
ll qpow(ll x,ll k=P-2) {
	ll res=1;
	for(;k;k>>=1,x=x*x%P) if(k&1) res=res*x%P;
	return res;
}
int n,m,W[12],F[12][N*2];
int A[N],B[N],D[N];
int ans;
ll X[20],Y[20],I[20];
int Lag(int n,int x){
	ll res=0;
	rep(i,0,n) {
		ll a=1,b=1;
		rep(j,0,n) if(i!=j) a=a*(P+x-X[j])%P,b=b*(X[i]<X[j]?-I[X[j]-X[i]]:I[X[i]-X[j]])%P;
		res=(res+a*b%P*Y[i])%P;
	}
	return res;
}
int main() {
	I[0]=I[1]=1;
	rep(i,2,19) I[i]=P-P/i*I[P%i]%P;
	n=rd(),m=rd();
	rep(i,1,m) W[i]=rd();
	rep(i,1,n) A[i]=rd(),B[i]=rd();
	int f=0;
	rep(i,1,m) {
		int c=F[i][0]=W[i],now=0,l=0,r=0;
		rep(j,1,n*2) {
			if(A[j<=n?j:j-n]==i) now+=B[j<=n?j:j-n];
			if(now<l) l=now,c--;
			if(now>r) r=now,c--;
			c=max(c,0),F[i][j]=c;
		}
		D[i]=abs(now)/2;
		if(now || c==0) f=1;
	}
	if(!f) return puts("-1"),0;
	rep(i,0,n){
		ll t=1;
		rep(j,1,m) t=t*F[j][i]%P;
		ans=(ans+t)%P;
	}
	rep(i,n+1,n*2) {
		int n=1e9,f=1;
		rep(j,1,m) {
			if(D[j]) n=min(n,F[j][i]/D[j]);
			f&=F[j][i]>0;
		}
		if(!f) continue;
		int t=1;
		rep(j,1,m) t=1ll*t*max(0,F[j][i]-D[j]*(n+1))%P;
		ans=(ans+t)%P;
		int s=0;
		rep(k,0,m+1) {
			int t=1;
			rep(j,1,m) t=1ll*t*(F[j][i]-D[j]*k)%P;
			X[k]=k,Y[k]=s=(s+t)%P;
		}
		ans=(ans+Lag(m+1,n))%P;
	}
	ans=(ans%P+P)%P,printf("%d\n",ans);
}