hdu2020多校-1
J Math is Simple
给定 (n) ，求
[sumlimits_{1le a<ble n \ gcd(a,b)=1 \ a+bge n} frac{1}{ab}
]
的值，答案对 (998244353) 取模。
Solution
令 (f_n = sumlimits_{1le a<ble n \ gcd(a,b)=1 \ a+bge n} frac{1}{ab}), (g_n = sumlimits_{1le a<ble n \ gcd(a,b)=1 \ a+b= n} frac{1}{ab})
显然有 (g_n = frac{1}{n} sum_{d=1}^{n} mu (d) frac{1}{d} sum_{t=1}^{frac{n}{d}} frac{1}{t})
再令 (h_n = sum_{i=1}^{n} frac{1}{i}) ，则有 (g_n = frac{1}{n} sum_{d | n} mu (d) frac{1}{d} h(frac{n}{d}))
推导 (f) 和 (g) 的关系：
[f_n = f_{n-1} + sumlimits_{1le ale n \ gcd(a,n) = 1}frac{1}{an} - sumlimits_{1le a<ble n \ gcd(a,b)=1 \ a+b=n-1} frac{1}{ab}
]
[f_n = f_{n-1} + g_n - g_{n-1}
]
[f_n = ... = f_2 + g_n - g_2 = frac{1}{2} + g_n
]
hdu2018多校-5
H Hills And Valleys
给定一个长度为 (n) 的序列 (a) ，你需要翻转一段区间 ([l,r]) 来最大化序列的最长不下降子序列。
求出最长不下降子序列长度以及翻转的区间。
数据范围: (1le nle 10^5, 0le a_ile 9)
Solution
枚举 ([x,y]) 表示翻转区间内产生贡献的数的值域范围，设 (b = { 0...x, y...x, y...9}) ，然后跑 (a) 和 (b) 的 (LCS) 即可，这里的 (b) 的数可多次被覆盖。
定义 (dp[i][j]) 表示 (a) 到 (i) , (b) 到 (j) 的 (LCS) ，显然有
[dp[i][j] = max(dp[i - 1][j] + (a[i] == b[j]), dp[i][j - 1])
]
枚举的过程中顺带维护 翻转区间的两端点 即可。
时间复杂度: (O(45*12*n)) ，跑不满。