题解：P14585 [LNCPC 2025] Entering the unknown

· · 题解

P14585 [LNCPC 2025] Entering the unknown 题解

赛时差 5 min 调出来qwq。

设下标为 i 的数的“数字”（即为题面中的最大出现数字）为 b_i。

原数组为 a_i。

这样问题就转化成了求 \sum_{l = 1}^n \sum_{r = l}^n [\max_{i = l}^r b[i] \mid \sum_{i = l}^r a[i]]。

然后随便敲个 st 表就可以打 O(n ^ 2) 暴力了（哈哈哈，我在 ICPC 赛制上打部分分）。

考虑优化，我们注意到，b 数组的取值仅为 [0,9]。

考虑由此入手，发现最大值具有可加性。

所以我们从大到小枚举可行的区间最大值。现在，我们要求区间和整除现在枚举的极大值的区间个数。

发现直接做不好做，考虑容斥。

发现我们可以 O(n) 做一段数中，有多少个区间的和整除某个值。

设现在枚举的最大值为 mx。

现在我们求出所有的所有区间和整除 mx 的区间，再减去区间和整除 mx 并且区间 \max b 不等于 mx 的区间个数就行。

至于怎么 O(n) 做这个东西呢？

只需要维护每个数的前缀和模 mx 意义下余数的出现次数即可。

形式化地说：

设点 i 的前缀和为 sum_i。

则一个合法区间 [l,r] 等价于 sum_r \equiv sum_{l - 1} \pmod {mx}。

特殊的 sum_0 为 0。

发现我们需要的只是 \sum{i = 0}^{r - 1} [sum_r \equiv sum_i \pmod {mx}]。

我们对于每一种余数记录出现次数即可。

特殊的，cnt_0 初始化为 0。

每次枚举 mx 后，将 b 数组为 mx 的所有点删除即可。

每次我们枚举所有的未删除连通块即可。

时间复杂度为 O(\sum n)。

跑的飞快！！！

最后感谢 @Pursuing_OIer 提供思路！

#include <iostream>
#include <stdio.h>
#include <bitset>
#include <algorithm>
#include <string.h>
#include <cmath>
#define int long long 
#define con putchar_unlocked(' ')
#define ent putchar_unlocked('\n')
#define Blue_Archive return 0
using namespace std;
constexpr int N = 1e5 + 3;
constexpr int mod = 1e9 + 7;
constexpr int INF = 0x7f7f7f7f7f7f7f7f;

int T;
int n;
int ans;
int top;
int a[N];
int mx[N];
int cnt[11];

struct miku
{
    int l,r;
}stk[N];

bitset<N> vis;

inline int get_max(int x)
{
    int res = 0;
    while(x) res = max(res,x % 10),x /= 10;
    return res;
}

inline int work(int op)
{
    int res = 0;
    for(int i = 1,sum;i <= top;i ++)
    {
        sum = 0;
        for(int j = 0;j < op;j ++) cnt[j] = 0;
        cnt[0] = 1;
        for(int j = stk[i].l;j <= stk[i].r;j ++)
        {
            sum += a[j];
            res += cnt[sum % op];
            cnt[sum % op] ++;
        }
    }
    top = 0;
    for(int i = 1;i <= n;i ++) if(mx[i] == op) vis[i] = 1;
    for(int l = 1,r;l <= n;l ++)
    {
        if(vis[l]) continue;
        r = l;
        while(!vis[r + 1] && r < n) r ++;
        stk[++ top] = {l,r};
        l = r;
    }
    for(int i = 1,sum;i <= top;i ++)
    {
        sum = 0;
        for(int j = 0;j < op;j ++) cnt[j] = 0;
        cnt[0] = 1;
        for(int j = stk[i].l;j <= stk[i].r;j ++)
        {
            sum += a[j];
            res -= cnt[sum % op];
            cnt[sum % op] ++;
        }
    }
    return res;
}

inline void solve()
{
    vis.reset();
    top = ans = 0;
    cin >> n;
    for(int i = 1;i <= n;i ++)
    {
        cin >> a[i];
        mx[i] = get_max(a[i]);
    }
    stk[++ top] = {1,n};
    for(int i = 9;i >= 1;i --) ans += work(i);
    cout << ans << '\n';
}

signed main()
{
    #ifndef ONLINE_JUDGE
        freopen("data.in","r",stdin);freopen("data.out","w",stdout);
    #endif
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> T;
    while(T --) solve();
    Blue_Archive;
}