[补]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);
}