题解：P14585 [LNCPC 2025] Entering the unknown

_LogicFish_qwq · 2026-10-20 16:43:32 · 题解

一种似乎符合人类思考方式的解法。以下将“数位的最大值”简称为带粗体的最大值。

思路

由于这里的最大值取值只有 10 种，所以我们可以考虑枚举最大值求解。具体地，对于每一个枚举的最大值 d，寻找每个数字最大值不超过 d 的区间，且区间和 sum 能被 d 整除的个数。注意，这里满足条件的区间，一定是所有数字的最大值都不大于 d。为了筛选出这些数字，我们可以把 n 个数的最大值都算一遍。
:::success[求“最大值”]

inline int GetDigit(int x){
    int res = 0;
    while(x)
        res = std::max(res, x % 10), x /= 10;
    return res;
}
void Solve(){
    //...
    rep(i, 1, n) digit[i] = GetDigit(a[i]);
    //...
}

::: 接下来就是计算方案数的事了。把最大值 超过 d 的数字 a_{i} 记作“不合法数字”，不超过 d 的 a_{i} 记作“合法数字”，于是数列就被不合法数字划分成了一堆区间。现在我们研究其中的某一个区间。
对于任何一个子区间，可以用前缀和高效判断是否能被 d 整除。用 cnt_{i} 表示对 d 取模后余数为 i 的（从 1 开始的）前缀和有多少个。初始 cnt_{0}=1，代表一个空区间。
那么，如果当前前缀和加到了第 i 个数，对 d 取余是 sum，就有 cnt_{sum} 个区间，满足区间和被 d 整除。为什么？因为 a\equiv b(\bmod d) \lrArr (a-b)\equiv 0 (\bmod d)。这样一来，对于 cnt_{sum}，其实等于“以 i 结尾的合法子区间的数量”。
或者说一句“人话”：我们前缀和多出了 sum 的余数，所以往前面找另一个前缀和取余是 sum 的，两个前缀和一减就是 d 的倍数了。这也解释了为什么要先加上 cnt_{sum} 再更新 cnt_{sum}：免得算上长度为 0 的区间。
然而这样写有个问题：其实我们求出来的是最大值不超过 d 的所有区间里，被 d 整除的个数，而非恰好是 d 的个数。这个怎么解决？
很简单，只需要减去 最大值不超过 d-1 的区间，被 \bm{d} 整除的个数就行了。下面函数里传入的参数 op 就是用来干这个的。
:::success[计算每个 d 的方案]

inline ll Calc(int d, int op){
    ll res = 0;
    cnt.resize(d);
    int sum = 0;
    auto Reset = [&](){
        std::fill(cnt.begin(), cnt.end(), 0);
        cnt[0] = 1, sum = 0;
    };
    Reset();
    rep(i, 1, n) valid[i] = (digit[i] <= d - op);
    rep(i, 1, n){
        if(valid[i]){//是连续的一段，继续算
            sum = (sum + a[i]) % d;
            res += cnt[sum], cnt[sum]++;
        }else Reset();//碰到不合法数字，数列断开，从下一个合法数字开始的区间重新计算，因此此处清空cnt等等。
    }
    return res;
}

::: 最后枚举 d，加在一起，就是答案了。

\boxed{ans = \sum_{d=1}^{9}\left(Calc(d,0)-Calc(d,1)\right)}

其中 Calc(1,1)=0，因为不存在最大值小于等于 0 的正整数。

代码

复杂度分析

::cute-table{tuack} |代码任务|复杂度|备注| |:-:|:-:|:-| |输入|\operatorname{O}(n)|仅考虑单组测试的复杂度。| |计算最大值|\operatorname{O}(n\log_{10}{n})|我们要枚举每个数位，但是这里的 \log_{10}n 不会超过 9，~~我觉得当成常数也是可以的~~。| |计算每个 d 的答案|\operatorname{O}(n)|枚举每个数计算的。如果硬要说，带一个 9 的常数（d 有九个取值）。| |输出|\operatorname{O}(1)|略。| |总复杂度（单组测试）|\operatorname{O}(n+9n+n\log_{10}n)\approx \operatorname{O}(n)|<| |总复杂度|\operatorname{O}(\sum n)|<|

Talk is cheap, show me the code.

:::success[AC Code]

//Someone tell Vedal there is a problem with my AI.
#include<iostream>
#include<cstdio>
//#include<iomanip>
#include<vector>
#include<bitset>
#define rep(v, s, e) for(int v = (s); v <= (e); v++)
#define dec(v, e, s) for(int v = (e); v >= (s); v--)
using ll = long long;
class IO{
    static const int SIN = 1 << 16, SOUT = 1 << 16;
    char ib[SIN], *ip, *iq, ob[SOUT], *op, *oq;
    static inline bool isDigit(int c){ return c >= '0' && c <= '9'; }
public:
    IO(){ ip = ib, iq = ib, op = ob, oq = ob + SOUT; }
    ~IO(){ fwrite(ob, 1, op - ob, stdout); fflush(stdout); }
    inline int gc(){
        if(ip == iq) iq = (ip = ib) + fread(ib, 1, SIN, stdin);
        return ip == iq ? EOF : (unsigned char)*ip++;
    }
    inline void pc(char c){
        if(op == oq) fwrite(ob, 1, SOUT, stdout), op = ob;
        *op++ = c;
    }
    template<typename T> inline bool ReadI(T &x){
        int c = gc();
        while(c != EOF && !isDigit(c) && c != '-') c = gc();
        if(c == EOF) return false;
        short f = c == '-' ? c = gc(), -1 : 1; x = 0;
        while(isDigit(c)) x = (x << 1) + (x << 3) + (c ^ 48) * f, c = gc();
        return true;
    }
    template<typename T> inline void WriteI(T x, char ed = ' '){
        __uint128_t y;
        if(x < 0) pc('-'), y = -(__uint128_t)x;
        else y = (__uint128_t)x;
        char tmp[48]; int t = 0;
        do tmp[t++] = (y % 10) ^ 48, y /= 10; while(y);
        while(t) pc(tmp[--t]);
        pc(ed);
    }
}io;
void Init(), PreSolve(), Input(), Solve(), Answer(), AC();
const int MAXN = 1e5;
int n, a[MAXN + 5];
ll ans;
int digit[MAXN + 5], sum[MAXN + 5];
std::vector<int> cnt;
std::bitset<MAXN + 5> valid;
inline ll Calc(int d, int op = 0);
inline int GetDigit(int x);
signed main(){
    AC();
    return 0;
}
void Init(){
    #ifndef ONLINE_JUDGE
    std::freopen("FILE.in" , "r", stdin );
    std::freopen("FILE.out", "w", stdout);
    #endif
}
void AC(){
    Init();
    int T = 1;
    io.ReadI(T);
    while(T--){
        PreSolve();
        Input();
        Solve();
        Answer();
    }
}
void PreSolve(){
    ans = 0;
}
void Input(){
    io.ReadI(n);
    rep(i, 1, n) io.ReadI(a[i]);
}
void Solve(){
    rep(i, 1, n) digit[i] = GetDigit(a[i]);
    rep(i, 1, 9) ans += Calc(i) - Calc(i, 1);
}
void Answer(){
    io.WriteI(ans, '\n');
}
inline int GetDigit(int x){
    int res = 0;
    while(x)
        res = std::max(res, x % 10), x /= 10;
    return res;
}
inline ll Calc(int d, int op){
    ll res = 0;
    cnt.resize(d);
    int sum = 0;
    auto Reset = [&](){
        std::fill(cnt.begin(), cnt.end(), 0);
        cnt[0] = 1, sum = 0;
    };
    Reset();
    rep(i, 1, n) valid[i] = (digit[i] <= d - op);
    rep(i, 1, n){
        if(valid[i]){
            sum = (sum + a[i]) % d;
            res += cnt[sum], cnt[sum]++;
        }else Reset();
    }
    return res;
}

:::