题解：P14585 [LNCPC 2025] Entering the unknown

· · 题解

P14585 [LNCPC 2025] Entering the unknown

题意简述

给定一个长度 n 的序列，问有多少个符合条件的非空子数组，它们的总和可以被数组中最大的单个数字整除。

考虑一下

暴力

首先肯定有暴力写法，我们枚举每个区间，统计区间和和最大的数字，然后看看能不能整除。但是显然，复杂度飞上天。

思考

计算最大数字还有前缀和一定是必不可少的。

我们把每个元素的最大数字计入数组 mxa_i，同时有前缀和数组 s_i。也就是我们要找所有对 (l,r) 使得 \max_{l\le i\le r}(mxa_i)\mid (s_r-s_{l-1})。 \ 记 \max_{l\le i\le r}(mxa_i)=p

同时可以看成，

(s_r-s_{l-1}) \bmod p = 0

那么也就是，

s_r-s_{l-1}\equiv 0 \pmod p s_r \equiv s_{l-1} \pmod p

那么我们要找所有 (l,r) 使得满足上述式子，且区间内包含 p。

现在思路就变得明确起来了，我们可以枚举每个 p，向左右扩展到最大的区间，然后依次枚举左右两边每个数在模 p 下的余数。对于每个余数，将左区间有该余数的个数和右区间有该余数的个数相乘，就是该余数的答案。显然，余数最大是 9，故将每个余数的结果加起来，就是最终的答案了。

区间的优化

我们将目光放到扩展区间上，我们需要的合法区间是 (l,r)，满足 \max_{l\le i\le r}(mxa_i)=p，嘶那不就是要左边右边第一个大于这个 p 的地方，这两个地方的中间就是我们要的区间啊。想到这里我们就有了单调栈。

若我们均向左右找第一个大于 p 的位置作为区间，显然是会出现重复统计的风险。

若使用该方法，假设在某个合法区间内出现两个 p 相等，在枚举 p_2 时，左右区间时总会出现一个 l\le p_1,p_2\le r，在枚举 p_1 的环节中同样有一个 l\le p_1,p_2\le r，这就重复统计了。

解决这个问题的方法也很简单，任意一边的条件改为第一个大于等于 p 的数就行了。

统计答案的优化

我们花 O(1) 找到了合法区间，同样也能用前缀和做统计左右区间各个模 p 下的余数个数。

定义一个数组 cnts[i][c][g] 表示每个前缀和 s_i 除以 c 余 g 的个数的前缀和，左右区间的个数就能用这个用 O(1) 时间算出来。

code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define rd read()
#define enter putchar('\n')
#define fo(a,b,c) for(int a = (b); a <= (c); ++a)
#define of(a,b,c) for(int a = (b); a >= (c); --a)
#define pii pair<int,int>
#define pb push_back
#define endl '\n'
#define interesting int
#define itn int
const int N = 1e5+7, M = 1e5+7, INF=0x3f3f3f3f;
const ll llINF=0x3f3f3f3f3f3f3f3f;
inline int read() {
    int x=0,f=1; char ch = getchar();
    while (ch<'0' || ch>'9') {if (ch == '-')f=-1;ch=getchar();}
    while (ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int T;
int n, a[N], mxa[N];
ll s[N];
int get(int x) {
    int mx = -1;
    while (x) mx = max(mx, x%10), x /= 10;
    return mx;
}
void Input() {
    n = rd;
    fo (i, 1, n) {
        a[i] = rd;
        s[i] = s[i-1]+a[i];
        mxa[i] = get(a[i]);
    }
}
ll cnts[N][10][10], pos_left[N], pos_right[N];
int st1[N], top1, st2[N], top2;
void init() {
    top1 = 0, top2 = 0;
    fo (c, 1, 9) {
        fo (g, 0, 9) cnts[0][c][g] = 0;
        cnts[0][c][0] = 1;
    }
    // cnts
    fo (i, 1, n) {
        fo (c, 1, 9) {
            fo (g, 0, 9) cnts[i][c][g] = cnts[i-1][c][g];
            cnts[i][c][s[i]%c]++;
        }
    }
    // 单调栈 任意一边算第一个大于等于
    fo (i, 1, n) pos_left[i] = 0, pos_right[i] = n+1;
    fo (i, 1, n) {
        while (top1 && mxa[st1[top1]] <= mxa[i]) pos_right[st1[top1--]] = i;
        st1[++top1] = i;
    }
    of (i, n, 1) {
        while (top2 && mxa[st2[top2]] < mxa[i]) pos_left[st2[top2--]] = i;
        st2[++top2] = i;
    }
}
void solve() {
    Input();
    init();
    ll ans = 0;
    fo (i, 1, n) {
        int le = pos_left[i], ri = pos_right[i];
        fo (g, 0, 9) {
            ll lef = (cnts[i-1][mxa[i]][g]-(le>0?cnts[le-1][mxa[i]][g]:0));
            ll rig = (cnts[ri-1][mxa[i]][g]-cnts[i-1][mxa[i]][g]);
            ans += lef*rig;
        }
    }
    printf("%lld\n", ans);
}
signed main() {
    T = rd;
    while(T--) solve();

    return 0;
}