zcmimi's blog
avatar
zc
2020-03-24 09:05:00
查看原题

点击跳转

离线解法: cdq分治

将问题转化为三维偏序

我们先找出对答案有贡献的点(i,j)满足的条件:

time_i<time_j

val_i<val_j,pos_i>pos_jval_i>val_j,pos_i<pos_j

avatar
zc
2020-03-23 17:38:00
查看原题

点击跳转

二维数点模板

avatar
zc
2020-03-23 16:44:00
查看原题

点击跳转

很妙的一道题

对每位置i分别统计[l,i],l\in [1,i]的方案数

S_i表示\sum_{j=1}^i [H_i \ge X],pre为位置i-1的方案数,now为位置i的方案数

H_i\ge x,now=pre+\sum_{j=1}^i [S_j=S_i],这些位置是位置i-1不能满足而位置i可以满足的

H_i\le x,now=pre-\sum_{j=1}^i [S_j=S_{i-1}],这些位置是位置i不能满足而位置i-1可以满足的

这样就可以\Theta(n)解决了呢

记得开long long,S_0先赋值为n,防止负数re

avatar
zc
2020-03-23 08:44:00
查看原题

点击跳转

avatar
zc
2020-03-23 00:30:00
查看原题

点击跳转

先离散化,然后用树状数组统计两边的数目,比较即可

avatar
zc
2020-03-22 23:49:00
查看原题

点击跳转

首先可以想到按v_i排序

接下来就直接按顺序插入并统计就可以了

关于距离之和的统计:

可以分前半部分和后半部分统计

用树状数组维护即可

感觉很水

具体看代码吧

avatar
zc
2020-03-21 23:31:00
查看原题

点击跳转

允许离线处理

可以看成三维偏序(坐标和时间)

考虑如果要求的点都在当前点的左上方

那么也就是要求x_j\le x_i,y_j\le y_i,time_j\le time_i

x_i+y_i-\max(x_j+y_j)

坐标再旋转并处理三次就可以了

avatar
zc
2020-03-20 21:22:00
查看原题

点击跳转

avatar
zc
2020-03-20 16:33:00
查看原题

点击跳转

\prod_{i=1}^n\prod_{j=1}^n\frac{lcm(i,j)}{\gcd(i,j)} \\ =\prod_{i=1}^n\prod_{j=1}^n\frac{ij}{\gcd(i,j)^2} \\ =\prod_{i=1}^n\prod_{j=1}^n ij \prod_{d=1}^n {\frac 1{d^2}}^{\sum_{i=1}^n\sum_{j=1}^n [\gcd(i,j)=d]} \\ =(n!)^{2n} \left (\prod_{d=1}^n d^{\sum_{i=1}^n\sum_{j=1}^n [\gcd(i,j)=d]} \right )^{-2}

其中:

\prod_{d=1}^n d^{\sum_{i=1}^n\sum_{j=1}^n [\gcd(i,j)=d]} \\ =\prod_{d=1}^n d^{\sum_{i=1}^{\left \lfloor \frac nd \right \rfloor}\sum_{j=1}^{\left \lfloor \frac nd \right \rfloor} [\gcd(i,j)=1]} \\ =\prod_{d=1}^n d^{-1+2\sum_{i=1}^{\left \lfloor \frac nd \right \rfloor} \varphi(i)}

因为mod=104857601是质数,使用可以用欧拉定理

avatar
zc
2020-03-20 12:57:00
查看原题

点击跳转

带 套 路 题

\sum_{i=1}^n\sum_{j=1}^n(i+j)^k\mu^2(\gcd(i,j))\gcd(i,j) \\ =\sum_{d=1}^n \mu^2(d) d \sum_{i=1}^n\sum_{j=1}^n(i+j)^k[\gcd(i,j)=d] \\ =\sum_{d=1}^n \mu^2(d) d^{k+1} \sum_{i=1}^{\left \lfloor \frac nd \right \rfloor}\sum_{j=1}^{\left \lfloor \frac nd \right \rfloor}(i+j)^k[\gcd(i,j)=1]

S(n)=\sum_{i=1}^n\sum_{j=1}^n(i+j)^k

=\sum_{d=1}^n \mu^2(d) d^{k+1} \sum_{i=1}^{\left \lfloor \frac nd \right \rfloor}\sum_{j=1}^{\left \lfloor \frac nd \right \rfloor}(i+j)^k \sum_{x|i,x|j} \mu(x) \\ =\sum_{d=1}^n \sum_{x=1}^{\left \lfloor \frac nd \right \rfloor}\mu^2(d) d^{k+1} \mu(x) x^k S(\left \lfloor \frac n{dx} \right \rfloor)

T=dx

=\sum_{T=1}^n \sum_{d|T} \mu^2(d) d^{k+1} \mu(\frac Td) (\frac Td)^k S(\left \lfloor \frac nT \right \rfloor) \\ =\sum_{T=1}^n S(\left \lfloor \frac nT \right \rfloor) T^k \sum_{d|T} d \mu^2(d)\mu(\frac Td)

如何快速求令S(n)?

设:

F(n)=\sum_{i=1}^n i^k

G(n)=\sum_{i=1}^n F(i)

那么

S(n)=\sum_{i=n+1}^{2n}F(i)-\sum_{i=1}^nF(i) \\ =G(2n)-2G(n)

筛出F的前缀和,然后筛S(n)

优化:

因为模数是质数,根据欧拉定理: 对于互质的a,n满足a^{\varphi(n)} \equiv 1\pmod n

可以k=k \mod 998244352

求后半部分

f(n)=\sum_{d|n} d \mu^2(d)\mu(\frac nd)

如何线性求f(n)?

f(n)是若干个积性函数的卷积,所以f(n)也是积性函数

那么f(n)=f(p^k)f(\frac n{p^k})

f(1)=1

f(p^1)=p-1(带入即可得到)

f(p^2)=-p(带入即可得到)

f(p^k)=0(k\ge 3)

d\frac nd中必然有一个有平方因子,所以\mu(d)\mu(\frac nd)必有一项为0

所以f(p^k)=0(k\ge 3)

接下来就可以线性筛f(n)

24/73
Search
search