The 6th Liaoning Provincial Collegiate Programming Contest-2025-辽宁省赛-E. Entering the unknown（≤d 比=d 好计数更多，那为什么不使用 f(≤d)-f(≤d-1) 得到 f(=d) 呢？）

题目大意

题目描述
给定一个长度为 $n$ 的正整数数组，求有多少个非空连续子数组满足以下条件：子数组内所有元素的和，能够被该子数组中所有元素包含的数字字符的最大值整除。

（注：数字字符指组成数字的 $0 \sim 9$。例如，数组 [2025, 11, 15] 中包含的数字字符有 $0, 1, 2, 5$，其最大值为 $5$。）

输入格式
第一行包含一个整数 $T$（$1 \le T \le 10^4$），表示测试用例的数量。
对于每个测试用例：
第一行包含一个整数 $n$（$1 \le n \le 10^5$），表示数组长度。
第二行包含 $n$ 个正整数 $x_1, x_2, \dots, x_n$（$1 \le x_i \le 10^9$），表示数组元素。
保证所有测试用例中 $n$ 的总和不超过 $10^5$。

输出格式
对于每个测试用例，输出一行一个整数，表示满足条件的非空子数组数量。

样例输入

2
3
213 12 21
7
314 880 246 170 493 474 129

样例输出

4
7

样例解释
以第一个测试用例 [213, 12, 21] 为例，考察其所有非空子数组：

• [213]：包含数字 $1, 2, 3$，最大数字为 $3$。子数组元素和为 $213$，$213 \bmod 3 = 0$，满足条件。

• [12]：包含数字 $1, 2$，最大数字为 $2$。子数组元素和为 $12$，$12 \bmod 2 = 0$，满足条件。

• [21]：包含数字 $1, 2$，最大数字为 $2$。子数组元素和为 $21$，$21 \bmod 2 \neq 0$，不满足条件。

• [213, 12]：包含数字 $1, 2, 3$，最大数字为 $3$。子数组元素和为 $213 + 12 = 225$，$225 \bmod 3 = 0$，满足条件。

• [12, 21]：包含数字 $1, 2$，最大数字为 $2$。子数组元素和为 $12 + 21 = 33$，$33 \bmod 2 \neq 0$，不满足条件。

• [213, 12, 21]：包含数字 $1, 2, 3$，最大数字为 $3$。子数组元素和为 $213 + 12 + 21 = 246$，$246 \bmod 3 = 0$，满足条件。

满足条件的子数组共有 4 个。

思路讲解

≤d 比=d 好计数得多，那为什么不使用 f(≤d)-f(≤d-1) 得到 f(=d) 呢？

不过，要注意到，就是光一个 d 是不够描述这个 f 函数的。

定义 $ f(≤d，big_d)$ 指的是最大 digit 是 $≤d$ 而且可以被 $big_d$ 整除的这个子段数量。

因此，不难发现 $ f(=d，big_d)=f(≤d,big_d)-f(≤d-1,big_d)$。

使用这一容斥方法解决该问题，是因为我们发现在编程中，我们发现，很难对 最大 digit=d 进行计数（你要是不信的话可以自此试试）。

for (int big_d=1;big_d<=9;++big_d) {
    vector<ll> F(10+2);
    for (int d=big_d-1;d<=big_d;++d) {
        vector<ll> R(big_d);
        for (int i=1;i<=N;++i) {
            if (mx_d[i]>d) {
                // if (find_mx) {
                //     ans+=R[0];
                // }
                R.assign(big_d,0);
                continue;
            }
            // cal(A[i]);
            ll rem=A[i]%big_d;
            rotate(R.rbegin(),R.rbegin()+rem,R.rend());
            R[rem]++;
            F[d]+=R[0];

            // if (find_mx) {
            //     ans+=R[0];
            // }
        }
    }
    ans+=F[big_d]-F[big_d-1];
}

AC代码

AC
https://codeforces.com/gym/106380/submission/366441214

源代码

/**
 * Problem: E. Entering the unknown
 * Contest: The 6th Liaoning Provincial Collegiate Programming Contest
 * Judge: Codeforces
 * URL: https://codeforces.com/gym/106380/problem/E
 * Created: 2026-03-12 19:47:36
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

/*
 *
 */

void Solve() {
    ll N;
    cin >> N;
    vector<ll> A(N+2);
    vector<ll> mx_d(N+2);
    for (int i=1;i<=N;++i) {
        cin>>A[i];
        string s=to_string(A[i]);
        mx_d[i]=*max_element(all(s))-'0';
    }
    ll ans=0;

    for (int big_d=1;big_d<=9;++big_d) {
        vector<ll> F(10+2);
        for (int d=big_d-1;d<=big_d;++d) {
            vector<ll> R(big_d);
            for (int i=1;i<=N;++i) {
                if (mx_d[i]>d) {
                    // if (find_mx) {
                    //     ans+=R[0];
                    // }
                    R.assign(big_d,0);
                    continue;
                }
                // cal(A[i]);
                ll rem=A[i]%big_d;
                rotate(R.rbegin(),R.rbegin()+rem,R.rend());
                R[rem]++;
                F[d]+=R[0];

                // if (find_mx) {
                //     ans+=R[0];
                // }
            }
        }
        ans+=F[big_d]-F[big_d-1];
    }
// #ifdef LOCAL
//     debug1d(F);
// #endif

    cout<<ans<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    cin >> lT;
    for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/gym/106380/submission/366441214

*/

心路历程（WA，TLE，MLE……）