2019暑假杭二day7测试总结

暑假杭二day7测试总结"/>

2019暑假杭二day7测试总结

2019暑假杭二day7测试总结

• T1
• • 题目大意
  • sol
• T2
• • 题目大意
  • sol
• T3
• • 题目大意
  • sol

T1

题目大意

求 ∑ i = 1 n ∑ j = 1 n μ ( g c d ( i , j ) ) % 998244253 , n ≤ 1 0 10 \sum_{i=1}^n\sum_{j=1}^n\mu(gcd(i,j))\%998244253,n\le 10^{10} ∑i=1n​∑j=1n​μ(gcd(i,j))%998244253,n≤1010

sol

∑ i = 1 n ∑ j = 1 n μ ( g c d ( i , j ) ) = ∑ k = 1 n ∑ i = 1 n ∑ j = 1 n μ ( k ) [ g c d ( i , j ) = k ] = ∑ k = 1 n μ ( k ) ∑ i = 1 ⌊ n k ⌋ ∑ j = 1 ⌊ n k ⌋ [ g c d ( i , j ) = 1 ] = ∑ k = 1 n μ ( k ) ∑ i = 1 ⌊ n k ⌋ ∑ j = 1 ⌊ n k ⌋ ∑ d ∣ i & d ∣ j μ ( d ) = ∑ k = 1 n μ ( k ) ∑ d = 1 ⌊ n k ⌋ μ ( d ) ∑ i = 1 ⌊ n k d ⌋ ∑ j = 1 ⌊ n k d ⌋ 令 s u m ( x ) = ∑ i = 1 n 1 则 原 式 = ∑ k = 1 n μ ( k ) ∑ d = 1 ⌊ n k ⌋ μ ( d ) s u m ( ⌊ n k d ⌋ ) 2 考 虑 枚 举 k × d 原 式 = ∑ T = 1 n ∑ d ∣ T μ ( d ) μ ( T d ) s u m ( ⌊ n k d ⌋ ) 2 令 f ( x ) = ∑ i ∣ x μ ( i ) μ ( x i ) = ( μ ∗ μ ) 原 式 = ∑ T = 1 n f ( T ) s u m ( ⌊ n T ⌋ ) 2 \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 i=1∑n​j=1∑n​μ(gcd(i,j))=k=1∑n​i=1∑n​j=1∑n​μ(k)[gcd(i,j)=k]=k=1∑n​μ(k)i=1∑⌊kn​⌋​j=1∑⌊kn​⌋​[gcd(i,j)=1]=k=1∑n​μ(k)i=1∑⌊kn​⌋​j=1∑⌊kn​⌋​d∣i&d∣j∑​μ(d)=k=1∑n​μ(k)d=1∑⌊kn​⌋​μ(d)i=1∑⌊kdn​⌋​j=1∑⌊kdn​⌋​令sum(x)=i=1∑n​1则原式=k=1∑n​μ(k)d=1∑⌊kn​⌋​μ(d)sum(⌊kdn​⌋)2考虑枚举k×d原式=T=1∑n​d∣T∑​μ(d)μ(dT​)sum(⌊kdn​⌋)2令f(x)=i∣x∑​μ(i)μ(ix​)=(μ∗μ)原式=T=1∑n​f(T)sum(⌊Tn​⌋)2
后面明显可以整除分块，问题变成了如何快速求 f ( x ) f(x) f(x)的前缀和，题解说可以用杜教筛，可我就是不会筛 ( μ ∗ μ ) (\mu*\mu) (μ∗μ)，只写出了线筛的分。

T2

题目大意

给定一个只包含小写字母的字符串 , 求其本质不同的子序列的个数， l e n ≤ 1 0 6 , a n s len \le 10^6,ans len≤106,ans对 998244353 998244353 998244353取模。

sol

我当时想了一个用tire树维护有多少个子序列，很明显方案数爆炸。

其实正解不需要任何数据结构，十分简单。

考虑递推，设f[i]为前i个字母组成的本质不同的子序列的个数。 f [ i ] = 2 f [ i − 1 ] f[i]=2f[i-1] f[i]=2f[i−1]。但这会有很多重复的，设 s i s_i si​为第i个字母，我们还需减去之前以 s i s_i si​结尾的子序列的个数，这些都被重复算了一次。以 s i s_i si​结尾的子序列的个数也可以递推，+=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 ，则 − x y a + k y = b -\frac{x}{y}a+\frac{k}{y}=b −yx​a+yk​=b，问题变成了给一个斜率固定的直线，过区间内的一些点使截距最小。然后变成了我不会的线段树维护凸壳。