世末少女，横渡月海

· · 题解

定义一次对于分数 \frac x y 的操作为以下两种选其一：使其变成 \frac{x+1}y 或使其变成 \frac x{y-1}，注意操作以后，分数不约分。

对于一个整数数组 \{b_i \} 和一个整数 k，定义 \text{MSF}(b,k) 为：

  • 对于数组 \frac 1{b_1},\frac 1{b_2},\dots,\frac1{b_m}，从中任选一个分数进行操作，重复 k 次操作，操作之后所有分数加起来的和的最大可能值。

给定长 n 的整数数组 \{a_i \} 与长 m 的整数数组 \{k_i \}，对于每个 k_i，求

\sum_{l=1}^n\sum_{r=l}^n\text{MSF}(a[l,r],k_i) \pmod{998244353}.

既然是求所有子区间的值的和，那就先来考虑怎么刻画 \text{MSF}(b,k)。

如果 b 只有一个数字，假设对其分母进行 p 次操作，即这个数变成 \frac{1+k-p}{b-p}，根据糖水不等式，有以下分讨：

考虑对于多个数字的情况，从简单的情况开始思考策略。假如说最后没有一个分数能大过 1，即我们进行的操作都是在分子上时，显然只对最大的 \frac 1{b_i} 操作是最好的。

如果有分数能大过 1，那肯定是先把最小的分母 b_i 减到 1，然后之后每次操作都可以加 1，赢麻了。

综上所述，我们的最优策略就是只对区间内最小的 b_i 进行操作，则 \text{MSF}(b,k) 被刻画为：

接下来就爽了，考虑处理一下贡献，设 i 位置左边第一个 \ge a_i 位置为 l'_i，右边第一个 >a_i 的位置为 r'_i，则所有 l_i'<l\le i\le r<r'_i 的区间 [l,r] 的最小值都是 i。

因此我们可以计算出一个点在多少个区间内是以最小值的身份贡献，在多少个区间内是以非最小值的贡献，可以推一下式子，这里是结果。

非最小值贡献是不变的，对于最小值，也就只是两个关于 k 的一次函数，预处理一次项系数和常数项的前缀和就可以了。l_i 和 r_i 用单调栈求。

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define llINF 0x3f3f3f3f3f3f3f3f
#define ui unsigned int
using namespace std;
const int N=5e5+10,P=998244353;
int qpow(int a,int k){
    int res=1;
    while(k){
        if(k&1) res=1ll*res*a%P;
        a=1ll*a*a%P,k>>=1;
    }
    return res;
}
int add(int x,int y){ return x+y>=P?x+y-P:x+y; }
int sub(int x,int y){ return x-y<0?x-y+P:x-y; }
int n,m,a[N],k[N],inva[N],c[N];
int l[N],r[N],stk[N],top;
int ord[N];
bool cmp(int x,int y){ return a[x]<a[y]; }
int sumR1[N],sumR0[N],sumL1[N],sumL0[N];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        inva[i]=qpow(a[i],P-2);
        ord[i]=i;
    }
    a[0]=-1,a[n+1]=-1;
    for(int i=1;i<=m;i++) cin>>k[i];
    stk[top=1]=0;
    for(int i=1;i<=n;i++){
        while(top&&a[stk[top]]>a[i]) top--;
        l[i]=stk[top],stk[++top]=i;
    }
    stk[top=1]=n+1;
    for(int i=n;i>=1;i--){
        while(top&&a[stk[top]]>=a[i]) top--;
        r[i]=stk[top],stk[++top]=i;
    }
    for(int i=1;i<=n;i++) c[i]=1ll*(i-l[i])*(r[i]-i)%P;
    int nonMin=0;
    for(int i=1;i<=n;i++) nonMin=add(nonMin,1ll*sub(1ll*i*(n-i+1)%P,c[i])*inva[i]%P);
    sort(ord+1,ord+n+1,cmp);
    for(int x=1;x<=n;x++){
        int i=ord[x];
        sumR1[x]=add(sumR1[x-1],1ll*c[i]*inva[i]%P);
        sumR0[x]=add(sumR0[x-1],1ll*c[i]*inva[i]%P);
        sumL1[x]=add(sumL1[x-1],c[i]);
        sumL0[x]=add(sumL0[x-1],1ll*c[i]*sub(2,a[i])%P);
    }<<nonMin<<"\n";
    int cur=0;
    for(int i=1;i<=m;i++){
        while(cur<n&&a[ord[cur+1]]<=k[i]) cur++;
        int res=nonMin;
        res=add(res,1ll*sumL1[cur]*k[i]%P);
        res=add(res,sumL0[cur]);
        res=add(res,1ll*sub(sumR1[n],sumR1[cur])*k[i]%P);
        res=add(res,sub(sumR0[n],sumR0[cur]));
        cout<<res<<"\n";
    }
    return 0;
}