ABC 353

目录

        C. Sigma Problem

        D. Another Sigma Problem 

---

 

 

 

C. Sigma Problem

 

        容斥。所有都先不取模，每个数出现 n - 1次，先算出不取模的答案。

        接下来找出哪些对之和超出了 1e8，统计这样的对的个数，再拿之前的答案减掉 个数 * 1e8

        只需要用二分就可以查找了， lower_bound(a + i + 1, a + n + 1, mod - a[i]) - a 的查找范围：

        [ i + 1, n ]

 

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e5 + 5, INF = 1e18, mod = 1e8;int T, n, cnt, tot, ans, a[N];
string s;signed main()
{cin >> n;for (int i = 1; i <= n; i ++){cin >> a[i];ans += a[i];}ans *= (n - 1);sort(a + 1, a + n + 1);for (int i = 1; i <= n; i ++){int pos = lower_bound(a + i + 1, a + n + 1, mod - a[i]) - a;ans -= (n + 1 - pos) * mod;}cout << ans;return 0;
}

 

若数组 a 的下标从 1 开始，要在闭区间 [l, r]（其中 l 和 r 分别代表左右端点的下标）内查找第一个大于或等于 x 的元素，lower_bound 的正确使用方式如下：int pos = lower_bound(a + l, a + r + 1, x) - a;

 

 

 

 

 

D. Another Sigma Problem 

 

        每一个 ai 作为 Ai 共 n - i 次，作为 Aj 共 i - 1 次，按每个数算贡献。

        g 数组一定要每一个都取模

        

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 5, INF = 1e18, mod = 998244353;int T, n, cnt, ans, a[N], c[N], d[N], g[N];
string s;int fpow(int a, int b)
{int res = 1;while (b){if (b & 1)res = res * a % mod;a = a * a % mod;b >>= 1;}return res;
}signed main()
{cin >> n;for (int i = 1; i <= n; i ++){cin >> a[i];s = to_string(a[i]);int len = s.length();c[i] = len;}g[n] = 0;for (int i = 1; i <= n; i ++)d[i] = fpow(10, c[i] % ( mod - 1));for (int i = n - 1; i >= 1; i --)g[i] = (g[i + 1] + d[i + 1]) % mod;for (int i = 1; i <= n; i ++){ans = (ans + a[i] * (i - 1) % mod) % mod;ans = (ans + a[i] * g[i] % mod) % mod;}cout << ans;return 0;
}