zcmimi's blog
avatar
zc
2019-12-31 11:31:00
查看原题

点击跳转

\overbrace{88...88}^{x\text{个}8}可以表示成:

8\times \frac{(10^x-1)}9

那么8\times \frac{(10^x-1)}9=kL

8\times (10^x-1)=9kL

d=\gcd(9L,8)=\gcd(8,L)

\frac{8}d\times (10^x-1)=\frac{9L}dk

p=\frac8d,q=\frac{9L}{d}

p\times (10^x-1)=qk

\because \gcd(p,q)=1

\therefore q|(10^x-1)

\frac{9L}{d}|(10^x-1)

10^x \equiv 1 \pmod {\frac{9L}{d}}

题目中要求的是最小的解

符合欧拉定理:

\gcd(a,p)=1,那么a^{\varphi(p)} \equiv 1 \pmod p

avatar
zc
2019-12-22 14:39:00
查看原题

点击跳转

此题卡常,需要使用二维树状数组

联想一维的树状数组:

差分数组:d_0=a_0,d_i=a_i-a_{i-1}(i>0)

令差分数组的前缀和sd_i=\sum_{j=0}^id_j,那么sd_i=a_i

我们现在来看看二维前缀和

s(i,j)=s(i-1,j)+s(i,j-1)-s(i-1,j-1)+a(i,j)

查询(x_1,y_1)(x_2,y_2)的和则为:

s(x_2,y_2)-s(x_1-1,y_2)-s(x_2,y_1-1)+s(x_1-1,y_1-1)

我们可以使用差分数组:

d(i,j)=a(i,j)-(a(i-1,j)+a(i,j-1)-a(i-1,j-1))

修改

d(x_1,y_1)+=v

d(x_1,y_2+1)-=v

d(x_2+1,y_1)-=v

d(x_2+1,y_2+1)+=v

举个例子:

0 0 0 0 0
0 1 1 1 0
0 1 1 1 0 
0 0 0 0 0

1部分加上v,那么

0  0 0 0 0
0 +v 0 0 -v
0  0 0 0 0 
0 -v 0 0 +v

查询

对于点(x,y)它的值应该是:\sum\limits_{i=1}^x\sum\limits_{j=1}^y d(i,j)

那么(1,1)(x,y)的和就是:

$$

\sum{i=1}^x\sum{j=1}^y\sum{p=1}^i\sum{q=1}^j d(p,q) \ =\sum{i=1}^x\sum{j=1}^yd(i,j)\times(x-i+1)\times(y-j+1) \ =\sum{i=1}^x\sum{j=1}^yd(i,j)\times[(xy-xj+x)+(-yi+ij-i)+(y-j+1)] \ =\sum{i=1}^x\sum{j=1}^yd(i,j)\times (xy+x+y+1)-d(i,j)\times i(y+1)-d(i,j)\times j(x+1) + d(i,j)\times i \times j $$

我们需要维护d(i,j),d(i,j)\times i,d(i,j) \times j, d(i,j)\times i \times j

avatar
zc
2019-12-22 13:54:00
查看原题

点击跳转

区间加,单点查询

设差分数组d_i=a_i-a_{i-1}

修改:d_l+=v,d_{r+1}-=v

查询:a_i=\sum\limits_{j=1}^id_j

区间加,区间查询

\sum_{i=1}^na_i=\sum_{i=1}^n\sum_{j=1}^id_i \\ =\sum_{i=1}^nd_i\times(n-i+1) \\ =n\sum_{i=1}^nd_i-\sum_{i=1}^n d_i\times(i-1)

维护两个树状数组,一个记录d_i,另一个记录d_i\times(i-1)

修改:

d_l+=v,d_{r+1}-=v

d'_l+=v\times(l-1),d'_{r+1}-=v\times(l-1)

查询:如上述

avatar
zc
2019-12-21 21:54:00
查看原题

点击跳转

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

f_{i,j} =f_{i,k}+1(|a_i-a_k| = |a_k-a_j|)

先对a排序,然后dp,双指针,记得数组开成short

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

因为有两条不同的路径,而且没有重边,所以这两个点就在同一个强连通分量里,直接tarjan一遍就可以

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

就是直接求中位数作那个点

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

构造1 \times n的矩阵X

矩阵满足

\because A \times B = C

\therefore X \times A \times B = X \times C

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

dp

(其实记忆化搜索也可以啦)

只要假设组成n的数是递增或递减,就不会重复了

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

39/74
Search
search