(2,1)

只要走的步数确定那么这个区间关于起点位置的相对位置也就确定了。

只要先算出每个循环向左/右所走的最远距离以及一个循环的移位即可。

这样考虑一个算法

先枚举走出区域的上一步走到了循环节中的哪个位置以及走了多少循环节。

由于不能走出区域于是可以根据每个维度的区间来算出这个维度的起点所在区间。

设下一步修改的维度为cc。

根据对应的dd容易算出这个维度的起点位置。

满足这个条件的基础上把其他维度的起点区间长度相乘就是起点数目。

考虑优化

那么不难发现每个维度的区间的相对位置即左右端点与起点的距离是关于xx的一次函数。

由于这一维度的方案数等于w1w1减去区间长度因此这也是关于xx的一次函数。

#include

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

{if(b1)jg1ll*jg*a%md;a1ll*a*a%md;b(b1);}return

jg;

Cc[i][j](Cc[i-1][j]Cc[i-1][j-1])%md;}}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

j0;ji;j)xs[i][i1-j]1ll*Cc[i1][j]*B[j]%md*ny%md;}

struct

{jg(jg1ll*j*xs[k][i])%md;j1ll*j*(n1)%md;}return

jg;

t(Sum(i,r)-Sum(i,l-1)md)%md;ans(ans1ll*sz[i]*t)%md;}return

ans;}

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;

SQj(max(a.l,b.l),min(a.r,b.r));

int

y0?SQj(-inf,inf):SQj(inf,-inf);if(x0)return

SQj(ceil(y,x),inf);

y0?SQj(-inf,inf):SQj(inf,-inf);if(x0)return

int

c1;ck;c)l[c]la[i][c],r[c]ra[i][c];for

(int

zl1-l[c],zrw[c]-r[c];if(c!C[(i1)%n])

{int

szr-zl1;if(s0)s0;jg1ll*jg*s%md;}

else

o1-t;if(ozlozr)s1;}jg1ll*jg*s%md;}}return

1ll*(i2)*jg%md;

n,k;scanf(%d%d,n,k);GetB(k);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

{la[i][j]al[j];ra[i][j]ar[j];}}bool

zdfalse;for

{if(i!C[0])ans1ll*ans*w[i]%md;}for

(int

{ans(anscal0(n,i,k))%md;//特殊处理x0的情况SLi

(int

taz[c]ra[i][c];if(ar[c]t)tar[c];r[c]SLi(az[c],t-az[c]);}

else

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

tzSLi(az[tc],aa[i][tc]);if(D[(i1)%n]1)ow[tc]-tz;

else

zl1-l[tc],zrw[tc]-r[tc];//tc这一维度起点的范围SQj

qjjiao(More(o,zl),Less(o,zr));//tc这一维度起点是确定的需要满足条件for

(int

{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

{if(c!tc)jiji*d[c];}ans(ansji.sum(qj.l,qj.r))%md;}printf(%d,(ans%mdmd)%md);return