题目大意
给定正整数数组 \(a_n\)，求有多少个连续子数组满足：它的和可以被组成它的所有数的这些十进制一位数中的最大的数（后续思路中我将简称为最大值）整除。
解题思路
第一次看到这题的时候，我一眼想到了今年东北赛的 A，那道题赛时没开掉后来补掉的，做法是二分 + ST 表。所以这题我也往这两个方向去想了。
首先注意到一个单调性：当固定一个左端点 \(l\) 时，这个区间的最大值随着右端点 \(r\) 的变化不会变小。于是枚举每一个 \(l\)，我们可以二分去找后面所有最大值变大的地方（最大值变大的地方不会超过 \(9\) 次，所以这里的时间复杂度是常数倍的 \(O(\log n)\) ），其中二分里的 check 可以用 ST 表去 \(O(1)\) 的得到区间最大值。
现在考虑它对答案的贡献是什么。容易注意到如果一个区间 \([l,r]\) 符合条件，那么设这段区间的最大值为 \(k\)，满足 \(k\mid (sum_r-sum_{l-1})\)，即 \(sum_r\equiv sum_{l-1}\pmod k\)。定义数组 \(cnt_{i,j,k}\) 表示
\(\sum_{l=1}^{i}[sum_l\equiv k\pmod j]\)，对于枚举的每一个左端点 \(l\)，最大值保持为 \(k\) 的一个最大的 \(r\) 的区间为 \([u,v]\)，对答案的贡献为 \(cnt_{v,k,sum_{l-1} \bmod k}-cnt_{u-1,k,sum_{l-1}\bmod k}\)。对于枚举到每一个 \(l\)，二分去找到每一个最大值变大的地方，记录答案即可。
令 \(c=9\)，时间复杂度为 \(O(c\times n\log n)\)，空间复杂度为 \(O(n\log n+nc^2)\)。
AC Code
#include<bits/stdc++.h>
#define int long long
#define mid ((l+r)>>1)
#define N 100005
using namespace std;
int a[N],sum[N];
int st[N][20],cnt[N][10][10];
int query(int l,int r)//ST表查询
{int len=(r-l+1);int ww=log2(len);int ans=max(st[l][ww],st[r-(1<<ww)+1][ww]);return ans;
}
signed main()
{int T=re();while(T--){int n=re();for(int i=1;i<=n;i++)a[i]=re(),sum[i]=sum[i-1]+a[i];for(int i=1;i<=n;i++)for(int j=1;j<=9;j++)for(int k=0;k<j;k++)cnt[i][j][k]=cnt[i-1][j][k]+(sum[i]%j==k);//计算 cnt int w=log2(n);for(int i=1;i<=n;i++){int maxx=0;int tem=a[i];while(tem){maxx=max(maxx,tem%10);tem/=10;}st[i][0]=maxx;//初始化 ST表 }for(int i=1;i<=w;i++)for(int j=1;j<=n-(1<<i)+1;j++)st[j][i]=max(st[j][i-1],st[j+(1<<(i-1))][i-1]);//预处理 ST表 int ans=0;for(int i=1;i<=n;i++)//枚举每一个左端点l {int maxx=query(i,i);int id=i;//id当前最大值为maxx的这一段的左端点 while(maxx!=query(i,n)){int l=id,r=n;while(l<r){if(query(i,mid)>maxx)r=mid;elsel=mid+1;}//找到最早增大的右端点 ans+=cnt[l-1][maxx][sum[i-1]%maxx]-cnt[id-1][maxx][sum[i-1]%maxx];//记录答案 id=l,maxx=query(i,id);//更新maxx和id }ans+=cnt[n][maxx][sum[i-1]%maxx]-cnt[id-1][maxx][sum[i-1]%maxx];//最后一段 }wr(ans),putchar('\n');}return 0;
}