AtCoder Beginner Contest 353
abc353_c
题意：定义\(F(x,y)\) 为\((x+y)mod10^8\)的值,求\(\displaystyle\sum_{i=1}^{N-1}\sum_{j=i+1}^Nf(A_i,A_j).\)
思路：对于\(\displaystyle\sum_{i=1}^{N-1}\sum_{j=i+1}^N\ f(A_i,A_j).\) 来说，每个\(A_i\)的次数都是\(n-1\)次，所以如果没有\(mod\ 10^8\)则\(ans=\displaystyle\sum_{i=1}^{N}(N-1)*A_i\)
因为\(A_i<10^8\)所以\(A_i+A_j<2·10^8\)，也就是说\(A_i+A_j\)只会超过\(10^8\)一倍，那么在 \(ans=\displaystyle\sum_{i=1}^{N}(N-1)*A_i\) 上减掉\(10^8\),从小到大排序后，对于每一个\(A_i\)求出对于有多少\(A_j\)相加会\(>10^8\)用二分查找
点击查看代码
abc353_d
题意：定义\(F(x,y)\)为\(A_x和A_y\) 数字拼接的结果，例如\(F(3,14)=314\)，求\(\displaystyle\sum_{i=1}^{N-1}\sum_{j=i+1}^NF(A_i,A_j)\ mod \ 998244353\)
思路：令\(dec（x）\)为x的位数，则\(F(A_i,A_j)=A_i*10^{dec(A_j)}+A_j\),所以\(\displaystyle\sum_{i=1}^{N-1}\sum_{j=i+1}^NF(A_i,A_j)=\displaystyle\sum_{i=1}^{N-1}\sum_{j=i+1}^NA_i*10^{dec(A_j)}+A_j=\displaystyle\sum_{i=1}^{N-1}\sum_{j=i+1}^NA_i*10^{dec(A_j)}+\sum_{i=1}^{N-1}\sum_{j=i+1}^NA_j\)
\(=\displaystyle\sum_{i=1}^{N-1}\sum_{j=i+1}^NA_i*10^{dec(A_j)}+\sum_{i=1}^{N}(i-1)*A_i\)
分开求即可
点击查看代码
abc353_e
题意：定义\(F(x,y)是字符串x和y的最长公共前缀的长度\)，求\(\displaystyle\sum_{i=1}^{N-1}\sum_{j=i+1}^{N}F(S_i,S_j)\)
思路：用trie数记录字符串，然后对于每一个字母x的cnt对答案的贡献是\(C_{cnt}^2\)
点击查看代码
