整数拼接

题目来源

www.acwing.com/problem/content/2070/

---

题目

给定一个长度为 n 的数组A1,A2,···,An。

你可以从中选出两个数 Ai 和 Aj(i 不等于 j)，然后将 Ai 和 Aj 一前一后拼成一个新的整数。

例如 12 和 345 可以拼成 12345 或 34512。

注意交换 Ai 和 Aj 的顺序总是被视为 2 种拼法，即便是 Ai=Aj 时。

请你计算有多少种拼法满足拼出的整数是 K 的倍数。

---

输入格式

第一行包含 22 个整数 nn 和 KK。

第二行包含 nn 个整数 A1,A2,⋅⋅⋅,AnA1,A2,···,An。

---

输出格式

一个整数代表答案。

数据范围

1≤n≤1051≤n≤105,

1≤K≤1051≤K≤105,

1≤Ai≤1091≤Ai≤109

---

输入样例

4 2
1 2 3 4

---

输出样例

6

---

暴力dfs枚举法

能过一部分数据

#include <iostream>
using namespace std;
typedef long long LL;
const int MAX = 10003;
LL num[MAX];
bool isUsed[MAX];
LL used[3];
int n,k;
int count;
void dfs(int lev){
    if(lev > 2){
        LL temp2 = used[2];
        LL temp1 = used[1];
        LL chen = 1;
        do{
            chen *= 10;
        }while(temp2/=10);
        temp1 = (used[1]%k)*(chen%k)%k;
        temp2 = used[2]%k;
        //cout<<used[1]<<used[2]<<":"<<temp1<<","<<temp2<<endl;
        if((temp1+temp2)%k== 0){
            count++;
        }
        return;
    }
    
    for(int i=0;i<n;i++){
        if(!isUsed[i]){
        	isUsed[i] = true;
            used[lev] = num[i];
            dfs(lev+1);
            isUsed[i] = false;
        }
    }
}
int main(){
    
    cin>>n>>k;
    for(int i = 0;i<n;i++){
        cin>>num[i];
    }
    dfs(1);
    cout<<count<<endl;
    return 0;
}

---

哈希表预处理再枚举

空间换时间

其中用到了一些数论的取模公式：

-
(a+b)%c = ((a%c)+(b%c))%c

-
(ab)%c = (a%c)(b%c)%c

-
(a-b)%c = ((a%c-b%c)+c)%c

#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
const int MAX = 100005;
LL num[MAX];
int hashTable[11][MAX];
//题目核心num[j]*10^leni%k = -num[i]%k
int main(){
    int n,k;
    cin>>n>>k;
    for(int i = 0;i<n;i++){
        cin>>num[i];
    }
    
    //预处理：任意一个num*10^leny%k的余数为x的数量(1<y<10)
    for(int i = 0;i<n;i++){
        LL chen = 1;
        for(int j = 1;j<11;j++){
            chen *= 10;
            int yu = ((num[i]%k)*(chen%k))%k;
            hashTable[j][yu]++;
        }
    }
    
    //枚举查找
    LL res = 0;
    for(int i = 0;i<n;i++){
        //-num[i]%k = (0+(-num[i]))%k = ((0%k)+(-num[i]%k))%k
        int len = to_string(num[i]).size();
        int yu = (k-num[i]%k)%k;
        res +=hashTable[len][yu];
        //判断是否存在选择自己与自己组合的情况->num[j]*10^leni%k = -num[i]%k
        LL chen = 1;
        while(len--){
            chen*=10;
        }
        if(yu == ((num[i]%k)*(chen%k))%k) res--;
    }
    
    
    cout<<res<<endl;
    return 0;
}

---