考虑如何计算贡献，显然的一般 (dp) 套路就是设 (f[i]) 为以 (i) 结尾的所有子区间的贡献。
但是这题我们发现这个结尾要和数字有关。所以先试着写一下普通的 (dp:)
(f[i][j]) 表示以 (i) 结尾的子区间中最后一个数字是 (j) 的价值和。
于是想到倒着做 (dp) 这一部分可以让这一步分解的数字与前文无关。
然后我们发现如果直接计算 extreme value 会很麻烦，直接加也是不好做的
所以我们想到能不能直接算贡献更简单，就考虑更改一下 (f[i][j]) 表示以 (i) 为左端点且分解完之后开头是 (j) 的方案数。
之所以需要这样是因为，考虑我们在一个序列的最前面加入一个数，如果它小于等于上一个数还好说，但是当它大于的时候会发现它的拆分并不是很好转移。
思路到这里就停了，实际上还是没有想明白怎么贪心做到最优解。
下面分析如何操作。
假定 (a_i>a_{i+1},) 那么我们需要把 (a_i) 分解为 (b_{1cdots k}) 满足 (b_1leq b_2leq ...leq b_k,b_kleq a_{i+1})
容易发现，我们需要让 (b) 的长度最小。那么当 (b_1) 最大的时候，即满足了贪心的要求，也满足了最短的要求。
这样我们考虑如何求 (b.) 我们发现，由于 (b_kleq a_{i+1},) 所以 (k=leftlceil frac{a_i}{a_{i+1}} ight ceil) 是能做到的最优解。
此时也可以做到 (b_1=leftlfloor frac{a_i}{k} ight floor)
那么这一个点的贡献就是 (k-1) 次了，分解后的最优解也就对应了 (b_1.)
这样下来就方便算贡献了。
考虑维护上一层出现的所有数字倒序 (dp,) 那么，对于 (f[i][j],) 它对答案的贡献是多少？
我们发现，设其对应修改次数是 (x,) 由 ([i+1][j']) 转移而来，那么它的贡献就是 (x imes f[i+1][j'] imes i)
这是因为，乘以 (i) 是和前面所有 (i) 个端点匹配都会有这样一个贡献，而乘以 (x) 是要和前面的方式组合起来。
维护一下决策点就可以做到 (O(nsqrt n)) 了。滚动数组优化一下空间即可。
#include<bits/stdc++.h>
using namespace std;
typedef double db;
#define int long long
const int mod=998244353;
const db eps=1e-14;
inline int Max(int x,int y){return x>y?x:y;}
inline int Min(int x,int y){return x<y?x:y;}
inline db Max(db x,db y){return x-y>eps?x:y;}
inline db Min(db x,db y){return x-y<eps?x:y;}
inline int Add(int x,int y,int M=mod){return (x+y)%M;}
inline int Mul(int x,int y,int M=mod){return 1ll*x*y%M;}
inline int Dec(int x,int y,int M=mod){return (x-y+M)%M;}
inline int Abs(int x){return x<0?-x:x;}
inline int read(){
int s=0,w=1;
char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch)){s=s*10+ch-'0';ch=getchar();}
return s*w;
}
inline void write(int x){
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+'0');
}
inline int qpow(int x,int y){
int res=1;
while(y){
if(y&1)res=Mul(res,x);
x=Mul(x,x);y>>=1;
}
return res;
}
typedef pair<int,int> pr;
#define fi first
#define se second
#define mk make_pair
#define pb emplace_back
#define poly vector<int>
const int N=2e5+10;
poly v[2];
int T,n,a[N];
int f[2][N];
signed main(){
T=read();
while(T--){
n=read();
for(int i=1;i<=n;++i)a[i]=read();
int ans=0,unq;
for(int i=n;i>=1;--i){
int pos=i&1;
v[pos].pb(a[i]);
f[pos][a[i]]=1;
unq=a[i];
for(auto x:v[pos^1]){
int fm=(a[i]+x-1)/x;
int num=a[i]/fm;
ans+=(fm-1)*f[pos^1][x]*i;
ans%=mod;
f[pos][num]+=f[pos^1][x];
f[pos][num]%=mod;
if(num!=unq){
unq=num;
v[pos].pb(unq);
}
}
for(auto x:v[pos^1])f[pos^1][x]=0;
v[pos^1].clear();
}
printf("%lld
",ans);
for(auto x:v[0])f[0][x]=0,f[1][x]=0;
for(auto x:v[1])f[1][x]=0,f[0][x]=0;
v[1].clear();
v[0].clear();
}
return 0;
}