整数拼接（参照acwing的yxc）

整数拼接给定一个长度为 n 的数组 A1,A2,⋅⋅⋅,An。你可以从中选出两个数 Ai 和 Aj(i 不等于 j)然后将 Ai 和 Aj 一前一后拼成一个新的整数。例如 12 和 345 可以拼成 12345 或 34512。注意交换 Ai 和 Aj 的顺序总是被视为 2 种拼法即便是 AiAj 时。请你计算有多少种拼法满足拼出的整数是 K 的倍数。输入格式第一行包含 2 个整数 n 和 K。第二行包含 n 个整数 A1,A2,⋅⋅⋅,An。输出格式一个整数代表答案。数据范围1≤n≤105,1≤K≤105,1≤Ai≤109输入样例4 2 1 2 3 4输出样例6代码1超时import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.math.BigInteger; public class Main { static int N100010; static long a[]new long[N]; // static int res[]new int[N]; //qq public static void main(String []args) throws IOException{ //System.out.println(1); BufferedReader brnew BufferedReader(new InputStreamReader(System.in)); //int nInteger.parseInt(br.readLine()); String g[]br.readLine().split( ); int nInteger.parseInt(g[0]),kInteger.parseInt(g[1]); gbr.readLine().split( ); for (int i 0; i n; i) { a[i]Long.parseLong(g[i]); } int res0; for (int i 0; i n; i) { for (int j i1; j n; j) { long a1a[i],a2a[j]; BigInteger b1new BigInteger(a1a2),b2new BigInteger(a2a1); if(b1.mod(BigInteger.valueOf(k)).equals(BigInteger.ZERO)){ res; } if(b2.mod(BigInteger.valueOf(k)).equals(BigInteger.ZERO)){ res; } } } System.out.println(res); } }代码2import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static int N100010; static int a[]new int[N]; static int s[][]new int[11][N]; //qq public static void main(String []args) throws IOException{ //System.out.println(1); BufferedReader brnew BufferedReader(new InputStreamReader(System.in)); //int nInteger.parseInt(br.readLine()); String g[]br.readLine().split( ); int nInteger.parseInt(g[0]),kInteger.parseInt(g[1]); gbr.readLine().split( ); for (int i 0; i n; i) { a[i]Integer.parseInt(g[i]); } //(A × 10^lenB B) mod k 0等价于 (A × 10^lenB) mod k (-B) mod k //等价于 (A × 10^lenB) mod k (k-B) mod k //开一个哈希表 第k个哈希表表示 aj*10^k %k 等于对应值 的个数 k为b的位数 //这样当b固定到时候 只需要去len(b)的哈希表里去找需要的余数就可以了 for (int i 0; i n; i) { int ta[i]%k; for (int j 0; j 11; j) { s[j][t]; tt*10%k; } } long res0; for (int i 0; i n; i) {//当固定一个b int ta[i]%k; int len (a[i] ).length(); ress[len][(k-t)%k]; //但是也有可能是自己拼自己 算一下是不是 是的话减去1 int rt; while(len0){ rr*10%k; len--; } if(r(k-t)%k)res--; } System.out.println(res); } }