题目大意:EndSaH 有 n 个数 a 1...n
，他打算选出这些数中的两个数进行拼接。一次拼数操作指的是将
x,y 两个正整数视作数字串，x 在前 y
在后拼接成一个新数字串，该新数字串所表示的正整数即这次拼数操作的结果。例如将
1234 与 56 拼数，将得到结果 123456。注意拼数操作是有顺序的，如拼接 56 与
1234 会得到 561234。但不知道为什么，EndSaH 一点也不喜欢 k
的倍数。他很好奇一个问题：有多少数对 (i,j)(1 ≤ i,j ≤ n,i ̸= j) 满足对 ai
与 aj 进行拼数操作后，结果不是 k
的倍数？由于他太菜了实在不会，只能向你求助了。
虽然我没有做对,但是非常喜欢的一道题,因为这道题思想太巧妙了
首先是套路:单步容斥,把问题转化成求多少对数是k的倍数
然后发现x与y拼数的实质是\(x \times
10^{log_{10}y + 1} +
y\),只要左边的数字与右边的数字加起来(对k取模之后)为k或者0即可
所以就有了如下做法:
先预处理一个桶mp[i][j]表示满足一个数乘上10的i次方后对k取模的结果为j的数的个数
然后考虑枚举每一个数字,O(1)查询他的另一半是否存在
注意要减去自己对自己的贡献...
就是自己找到自己会变成的模样,提前减一,事后再加回来
代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| #include <bits/stdc++.h>
#define int long long
#define ll long long
using namespace std;
const int N = 2e5 + 2;
map<int, int>mp[12];
int n, k, maxv, res;
int a[N];
inline int div(int x)
{
int ret(0);
while (x) ++ ret, x /= 10;
return ret;
}
signed main()
{
int i, j;
n = read(), k = read();
for (i = 1; i <= n; ++ i) a[i] = read(), maxv = max(maxv, div(a[i]));
for (i = 1; i <= n; ++ i)
{
int tmp = a[i];
for (j = 1; j <= maxv; ++ j)
{
tmp = tmp * 10 % k;
++ mp[j][tmp];
}
}
for (i = 1; i <= n; ++ i)
{
int tmp = a[i], nod = div(tmp);
for (j = 1; j <= nod; ++ j) tmp = tmp * 10 % k;
-- mp[nod][tmp];
if (a[i] % k) res += mp[nod][k - a[i] % k];
else res += mp[nod][0];
++ mp[nod][tmp];
}
put(n * (n - 1) - res);
return 0;
}
|
后记:
思想极其棒的题目
要注意以后再碰到这样"拼数字对某个数字取模统计多少个符合条件单步容斥"要有思路