咸阳网站建设公司电话,做个公司网站大概多少钱,wordpress 导航下拉,wordpress 美化网站题目#xff1a; 样例解释#xff1a; 【样例 #1 解释】 从 (1,1) 出发将走 2 步#xff0c;从 (1,2) 出发将走 4 步#xff0c;从 (1,3) 出发将走 4 步。 从 (2,1) 出发将走 2 步#xff0c;从 (2,2) 出发将走 3 步#xff0c;从 (2,3) 出发将走 3 步。 从 (3,1) 出发将…题目 样例解释 【样例 #1 解释】 从 (1,1) 出发将走 2 步从 (1,2) 出发将走 4 步从 (1,3) 出发将走 4 步。 从 (2,1) 出发将走 2 步从 (2,2) 出发将走 3 步从 (2,3) 出发将走 3 步。 从 (3,1) 出发将走 1 步从 (3,2) 出发将走 1 步从 (3,3) 出发将走 1 步。 共计 21 步。 思路 先考虑O(nkw)O(nkw)的30分暴力。 显然每个维度上走过的位置是一个区间。 只要走的步数确定那么这个区间关于起点位置的相对位置也就确定了。 只要先算出每个循环向左/右所走的最远距离以及一个循环的移位即可。 这样考虑一个算法 枚举走了多少步结束并算出贡献就是算出满足条件的起点数目。 先枚举走出区域的上一步走到了循环节中的哪个位置以及走了多少循环节。 由于不能走出区域于是可以根据每个维度的区间来算出这个维度的起点所在区间。 设下一步修改的维度为cc。根据对应的dd容易算出这个维度的起点位置。 那么这个位置必须在起点区间内。 满足这个条件的基础上把其他维度的起点区间长度相乘就是起点数目。 考虑优化 这个算法的主要瓶颈在于对循环节数的枚举。 设走过的循环节数目为xx。 那么不难发现每个维度的区间的相对位置即左右端点与起点的距离是关于xx的一次函数。 由于这一维度的方案数等于w1w1减去区间长度因此这也是关于xx的一次函数。 根据这个区间长度为正数可以得出xx的取值范围。 同时维度cc的起点位置也是关于xx的一次函数。 根据这个位置必须在起点区间内部进一步缩小xx的取值范围。 这样答案就是对于每个xx这些一次函数在xx处的值的乘积的和。 暴力进行多项式乘法并用自然数幂前缀和即可。 时间复杂度O(nk2)O(nk2)。 注意这个写法可能要对x0x0进行特判。 代码
#include stdio.h
#define inf 1999999999
#define md 1000000007
#define min(a,b) ab?a:b
#define max(a,b) ab?a:b
int az[12],al[12],ar[12],w[12],aa[500010][12];
int B[12],C[500010],D[500010],la[500010][12],ra[500010][12];
int ksm(int a,int b) {int jg1;while(b0) {if(b1)jg1ll*jg*a%md;a1ll*a*a%md;b(b1);}return jg;
}
int Cc[12][12],xs[12][12];
void GetB(int k)//伯努利数
{B[0]1;for (int i1;ik1;i) {for (int j0;ji;j) {if(j0||ji)Cc[i][j]1; else Cc[i][j](Cc[i-1][j]Cc[i-1][j-1])%md;}}for (int i1;ik;i) {int h0;for (int j0;ji;j)h(h1ll*Cc[i1][j]*B[j])%md;B[i]1ll*(md-h)*ksm(i1,md-2)%md;}for (int i1;ik;i) {int nyksm(i1,md-2);for (int j0;ji;j)xs[i][i1-j]1ll*Cc[i1][j]*B[j]%md*ny%md;}
}
struct SLi//一次函数
{int k,b;SLi() {}SLi(int K,int B) {kK;bB;}SLi(int Z) {k0;bZ;}
};
SLi operator-(const SLi x,const SLi y) {return SLi(x.k-y.k,x.b-y.b);
}
int Sum(int k,int n) {if(k0)return n1;int jg0;for (int i0,j1;ik1;i) {jg(jg1ll*j*xs[k][i])%md;j1ll*j*(n1)%md;}return jg;
}
struct DXS//多项式
{int sz[12],n;void operator(const DXS a) {na.n;for (int i0;in;i)sz[i]a.sz[i];}void clear() {for (int i1;i10;i)sz[i]0;sz[0]1;n0;}int sum(int l,int r) {int ans0;for (int i0;in;i) {int t(Sum(i,r)-Sum(i,l-1)md)%md;ans(ans1ll*sz[i]*t)%md;}return ans;}
};
DXS operator*(const DXSx,const SLiy) {DXS rt;rt.nx.n1;rt.sz[rt.n]0;for (int i0;ix.n;i)rt.sz[i]1ll*y.b*x.sz[i]%md;for (int i0;ix.n;i)rt.sz[i1](rt.sz[i1]1ll*y.k*x.sz[i])%md;return rt;
}
struct SQj//维护区间
{int l,r;SQj() {}SQj(int L,int R) {lL;rR;}
};
SQj jiao(const SQja,const SQjb) {return SQj(max(a.l,b.l),min(a.r,b.r));
}
int floor(int,int);
int ceil(int x,int y) {if(y0)x-x,y-y;if(x0)return (xy-1)/y;return -floor(-x,y);
}
int floor(int x,int y) {if(y0)x-x,y-y;if(x0)return x/y;return -ceil(-x,y);
}
SQj Less(SLi a,SLi b) {int xa.k-b.k,yb.b-a.b;if(x0)return y0?SQj(-inf,inf):SQj(inf,-inf);if(x0)return SQj(-inf,floor(y,x));return SQj(ceil(y,x),inf);
}
SQj More(SLi a,SLi b) {int xa.k-b.k,yb.b-a.b;if(x0)return y0?SQj(-inf,inf):SQj(inf,-inf);if(x0)return SQj(ceil(y,x),inf);return SQj(-inf,floor(y,x));
}
int cal0(int n,int i,int k) {int l[12],r[12],jg1;for (int c1;ck;c)l[c]la[i][c],r[c]ra[i][c];for (int c1;ck;c) {int zl1-l[c],zrw[c]-r[c];if(c!C[(i1)%n]) {int szr-zl1;if(s0)s0;jg1ll*jg*s%md;} else {int taa[i][c],s0;if(D[(i1)%n]1) {int ow[c]-t;if(ozlozr)s1;} else {int o1-t;if(ozlozr)s1;}jg1ll*jg*s%md;}}return 1ll*(i2)*jg%md;
}
int main() {int n,k;scanf(%d%d,n,k);GetB(k);for (int i1;ik;i)scanf(%d,w[i]);for (int i0;in;i) {scanf(%d%d,C[i],D[i]);if(i0) {for (int j1;jk;j)aa[i][j]aa[i-1][j];}aa[i][C[i]]D[i];//循环节中某一前缀的偏移量az[C[i]]D[i];if(az[C[i]]al[C[i]])//最左移位al[C[i]]az[C[i]];if(az[C[i]]ar[C[i]])//最右移位ar[C[i]]az[C[i]];for (int j1;jk;j) {la[i][j]al[j];ra[i][j]ar[j];}}bool zdfalse;for (int i1;ik;i) {if(az[i]!0||ar[i]-al[i]w[i]) {zdtrue;break;}}if(!zd)//走不出去 {printf(-1);return 0;}int ans1;for (int i1;ik;i) {if(i!C[0])ans1ll*ans*w[i]%md;}for (int i0;in;i) {ans(anscal0(n,i,k))%md;//特殊处理x0的情况SLi l[12],r[12],d[12];for (int c1;ck;c)//算出对应维度的一次函数 {if(az[c]0) {l[c]al[c];int taz[c]ra[i][c];if(ar[c]t)tar[c];r[c]SLi(az[c],t-az[c]);} else {r[c]ar[c];int taz[c]la[i][c];if(al[c]t)tal[c];l[c]SLi(az[c],t-az[c]);}d[c]r[c]-l[c];}int tcC[(i1)%n];SLi o;SLi tzSLi(az[tc],aa[i][tc]);if(D[(i1)%n]1)ow[tc]-tz; else o1-tz;SLi zl1-l[tc],zrw[tc]-r[tc];//tc这一维度起点的范围SQj qjjiao(More(o,zl),Less(o,zr));//tc这一维度起点是确定的需要满足条件for (int i1;ik;i) {d[i]w[i]-d[i];qjjiao(qj,More(d[i],1));//方案数0}qjjiao(qj,SQj(1,inf));if(qj.lqj.r)continue;DXS ji;ji.clear();jiji*SLi(n,i2);for (int c1;ck;c)//对应维度相乘 {if(c!tc)jiji*d[c];}ans(ansji.sum(qj.l,qj.r))%md;}printf(%d,(ans%mdmd)%md);return 0;
}
