2019暑假杭二day7測試總結

[toc]

T1

題目大意

求$\sum_{i=1}^n\sum_{j=1}n\mu(gcd(i,j))%998244253,n\le 10{10}$

sol

\[ \sum_{i=1}^n\sum_{j=1}^n\mu(gcd(i,j))\\ =\sum_{k=1}^n\sum_{i=1}^n\sum_{j=1}^n\mu(k)[gcd(i,j)=k]\\ =\sum_{k=1}^n\mu(k)\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{k}\rfloor}[gcd(i,j)=1]\\ =\sum_{k=1}^n\mu(k)\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{d|i\&d|j}\mu(d)\\ =\sum_{k=1}^n\mu(k)\sum_{d=1}^{\lfloor\frac{n}{k}\rfloor}\mu(d)\sum_{i=1}^{\lfloor\frac{n}{kd}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{kd}\rfloor}\\ 令sum(x)=\sum_{i=1}^n1\\ 則原式=\sum_{k=1}^n\mu(k)\sum_{d=1}^{\lfloor\frac{n}{k}\rfloor}\mu(d)sum({\lfloor\frac{n}{kd}\rfloor})^2\\ 考慮枚舉k\times d\\ 原式=\sum_{T=1}^n\sum_{d|T}\mu(d)\mu(\frac{T}{d})sum({\lfloor\frac{n}{kd}\rfloor})^2\\ 令f(x)=\sum_{i|x}\mu(i)\mu(\frac{x}{i})=(\mu*\mu)\\ 原式=\sum_{T=1}^nf(T)sum(\lfloor\frac{n}{T}\rfloor)^2 \]

後面明顯可以整除分塊，問題變成了如何快速求$f(x)\(的字首和，題解說可以用杜教篩，可我就是不會篩\)(\mu*\mu)$，隻寫出了線篩的分。

T2

題目大意

給定一個隻包含小寫字母的字元串 , 求其本質不同的子序列的個數，$len \le 10^6,ans$對$998244353$取模。

sol

我當時想了一個用tire樹維護有多少個子序列，很明顯方案數爆炸。

其實正解不需要任何資料結構，十分簡單。

考慮遞推，設f[i]為前i個字母組成的本質不同的子序列的個數。\(f[i]=2f[i-1]\)。但這會有很多重複的，設$s_i$為第i個字母，我們還需減去之前以$s_i$結尾的子序列的個數，這些都被重複算了一次。以$s_i$結尾的子序列的個數也可以遞推，+=f[i]-f[i-1]就行，因為多産生了這麼多貢獻。

T3

題目大意

請你維護一個初始為空的點的集合,支援以下操作:

• A x y 加入點 (x,y)
• Q l r x y 詢問點 (x,y) 與第 l 個 r 到個點的比對度的最大值

點 (x,y) 與 (a,b) 的比對度為 ax+by

sol

我隻寫了暴力。

正解把這個問題轉為了幾何問題，設 ax+by=k ，則 \(-\frac{x}{y}a+\frac{k}{y}=b\)，問題變成了給一個斜率固定的直線，過區間内的一些點使截距最小。然後變成了我不會的線段樹維護凸殼。

轉載于:https://www.cnblogs.com/hht2005/p/11402646.html