题面
题目描述
给定含n个整数的数组a。
规定数x,y的合并为xy。如：数12与数3456的合并为数123456。
有数组中的位置对(i,j)(i≠j)，计算使ai,aj的合并能被k整除的位置对数量。
输入
第一行输入整数n,k (1≤n≤2*10^5,2≤k≤10^9)
第二行输入含n个整数的数组a1,a2,a3,...,an (1≤ai≤10^9)
输出
输出位置对(i,j)的数量，使ai,aj的合并能被k整除
样例输入1
6 11
45 1 10 12 11 7
样例输出1
7
样例输入2
4 2
2 78 4 10
样例输出2
12
样例输入2
5 2
3 7 19 3 3
样例输出2
0
提示
样例输出1中，有位置对(1,2),(1,3),(2,3),(3,1),(3,4),(4,2),(4,3)，使所得数451,4510,110,1045,1012,121,1210能被11整除。
样例输出2中，全体位置对所得数都能被2整除。
样例输出3中，全体位置对所得数都不能被2整除。
题解
两数合并有计算公式$conc(a_i ,a_j ) = a_i cdot 10^{len[j]} + a_j$ (len[j]表示的位数)
若暴力枚举，时间复杂度达$O(n^2 )$，必超时。可以想到用利用计算公式分解两数的模，计算$a_j$的模并排序，枚举$a_i cdot 10^{len[j]}$取模并二分查找对应$a_j$的模的数量。这样就利用了排序与二分查找，减少了逐个枚举$a_j$部分的时间。
根据题意可知$(a_i cdot 10^{len[j]} + a_j {rm{) mod }}k = 0$,顺推得到$({rm{ }}(a_i cdot 10^{len[j]} {rm{ mod }}k) + (a_j {rm{ mod }}k{rm{) ) mod }}k = 0 Leftrightarrow k - (a_i cdot 10^{len[j]} {rm{ mod }}k) = a_j {rm{ mod }}k$。细节上，由于数组a中数的长度参差不齐，于是可以用“mod”二维数组存放长度为len[i]的数 mod k的值并排序。接着i=1 to n,j=1 to 10枚举$a_i cdot 10^j$部分，用lower_bound、upper_bound查找符合题意的低位部分的区间，累加这个区间即得到答案。
最终将时间复杂度$O(n^2 )$缩短为$O(10 cdot nlog n)$。
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 typedef long long ll; 5 int n, k; 6 int a[200005],len[200005]; 7 int mod[11][200005], mod_10[11]; 8 int cnt[11]; 9 10 int main() 11 { 12 scanf("%d%d", &n, &k); 13 for (int i = 1; i <= n; i++) 14 scanf("%d", a + i); 15 mod_10[0] = 1; 16 for (int i = 0; i < 10; i++) 17 mod_10[i + 1] = mod_10[i] * 10 % k; //计算10^n的模 18 for (int i = 1; i <= n; i++) 19 { 20 int x = a[i]; 21 while (x) 22 { 23 len[i]++; 24 x /= 10; 25 } 26 mod[len[i]][++cnt[len[i]]] = a[i] % k; 27 } 28 for (int i = 1; i <= 10; i++) 29 sort(mod[i] + 1, mod[i] + cnt[i] + 1); 30 ll ans = 0; 31 int mod1, mod2, *l, *r; 32 for (int i = 1; i <= n; i++) 33 { 34 for (int j = 1; j <= 10; j++) 35 { 36 mod1 = ((ll)a[i] * mod_10[j]) % k; //谨防int溢出! 37 mod2 = (k - mod1) % k; 38 l = lower_bound(mod[j] + 1, mod[j] + cnt[j] + 1, mod2); 39 r = upper_bound(mod[j] + 1, mod[j] + cnt[j] + 1, mod2); 40 ans += (len[i] == j && (mod1 + a[i] % k) % k == 0)?(r - l - 1):(r - l); 41 //此时状态包含位置对(i,i)且满足条件时减去该方案 42 } 43 } 44 printf("%lld", ans); 45 return 0; 46 }
- 还没有人评论，欢迎说说您的想法！
客服
