The 6th Liaoning Provincial Collegiate Programming Contest-2025-辽宁省赛-E. Entering the unknown（≤d 比=d 好计数更多，那为什么不使用 f(≤d)-f(≤d-1) 得到 f(=d) 呢？） · znzryb
## 题目大意
**题目描述**
给定一个长度为 $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 进行计数（你要是不信的话可以自此试试）。
```cpp
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](https://codeforces.com/gym/106380/submission/366441214)
::: 源代码
```cpp
/**
* 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……）