https://www.acwing.com/problem/content/description/2070/：

首先我们考虑两个数拼接：a[i] + a[j] 实际上就是$a[i] * 10^{length(a[j])} + a[j]$

即有：$a[i] * 10^{length(a[j])} + a[j] mod k == 0$

$a[i] * 10^{length(a[j])} mod k == -a[j] mod k$

也就是说这两者同余k的时候成立，这就很简单了。

我们预处理出长度为10 ^ i时候的每个数作为高位，然后一次性计算即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int N = 1e5 + 5;
const int M = 1e7 + 5;
const LL Mod = 998244353;
#define INF 1e14
#define dbg(ax) cout << "now this num is " << ax << endl;
inline long long ADD(long long x,long long y) {
    if(x + y < 0) return ((x + y) % Mod + Mod) % Mod;
    return (x + y) % Mod;
}
inline long long MUL(long long x,long long y) {
    if(x * y < 0) return ((x * y) % Mod + Mod) % Mod;
    return x * y % Mod;
}
inline long long DEC(long long x,long long y) {
    if(x - y < 0) return (x - y + Mod) % Mod;
    return (x - y) % Mod;
}

int n;
LL pw[20],cnt[20][N],mod,a[N];
void init() {
    pw[0] = 1;
    for(int i = 1;i <= 10;++i) pw[i] = pw[i - 1] * 10;
}
int get_len(int x) {
    int len = 0;
    while(x) {
        len++;
        x /= 10;
    }
    return len;
}
void solve() {
    scanf("%d %d",&n,&mod);
    for(int i = 1;i <= n;++i) scanf("%lld",&a[i]);
    for(int i = 1;i <= 10;++i) {
        for(int j = 1;j <= n;++j) {
            int ma = a[j] % mod * pw[i] % mod;
            cnt[i][ma]++;
        }
    }
    LL ans = 0;
    for(int i = 1;i <= n;++i) {
        int len = get_len(a[i]);
        int tmp = (-a[i] % mod + mod) % mod;
        LL ss = a[i] % mod * pw[len] % mod;
        ans += cnt[len][tmp];
        if(ss % mod == tmp) ans--;
    }
    printf("%lld\n",ans);
}   
int main() {
    init();
    // int _;
    // for(scanf("%d",&_);_;_--) {
        solve();
    //}
    system("pause");
    return 0;
}

View Code

https://www.acwing.com/problem/content/1232/

这题也是个关于模数的题：不过比较简单用经典的前缀和取模即可计算。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int N = 1e5 + 5;
const int M = 1e7 + 5;
const LL Mod = 998244353;
#define INF 1e14
#define dbg(ax) cout << "now this num is " << ax << endl;
inline long long ADD(long long x,long long y) {
    if(x + y < 0) return ((x + y) % Mod + Mod) % Mod;
    return (x + y) % Mod;
}
inline long long MUL(long long x,long long y) {
    if(x * y < 0) return ((x * y) % Mod + Mod) % Mod;
    return x * y % Mod;
}
inline long long DEC(long long x,long long y) {
    if(x - y < 0) return (x - y + Mod) % Mod;
    return (x - y) % Mod;
}

int n,k,a[N],cnt[N];
void solve() {
    scanf("%d %d",&n,&k);
    for(int i = 1;i <= n;++i) scanf("%d",&a[i]);
    int sum = 0;
    LL ans = 0;
    for(int i = 1;i <= n;++i) {
        sum += a[i];
        sum %= k;
        ans += cnt[sum];
        cnt[sum]++;
        if(sum == 0) ans++;
    }
    printf("%lld\n",ans);
}   
int main() {
    // int _;
    // for(scanf("%d",&_);_;_--) {
        solve();
    //}
    system("pause");
    return 0;
}

View Code