Codeforces1603 C.Extreme Extension DP 根号性质

Codeforces1603 C.Extreme Extension DP 根号性质

题意

定义对区间([l,r])的extreme values为

每次操作选择一个下标(index)，将(a_{index})拆分为(x,y)满足(x + y = a_{index})

最后使得区间([l,r])非递减的总操作次数

求([1,n])的每个子数组的extrme values的和

[1 leq n leq 10^5\ 1 leq a_i leq 10^5 ]

分析

首先解决只有一个询问([1,n])的答案如何计算

对于(a_i,a_{i+1})，如果(a_i < a_{i+1}) 显然不做任何操作更优

否则应该在(x_{max} < a_{i+1})的条件下使得(x_{min}) 取到最大值，不难发现这样的操作方法就是拆分为(lceilfrac{a_{i}}{a_{i+1}} ceil)个数，令最大的取(lfloorfrac{a_i}{lceilfrac{a_{i}}{a_{i+1}} ceil} floor)

于是如果只是求([1,n])就可以从后往前扫一遍求出答案

现在考虑子问题，考虑(dp_{i,j})表示第(i)个数作为开始，且拆分出的最小的数为(j)的方案

那么(dp_{i-1,lfloorfrac{a_i}{lceilfrac{a_{i}}{j} ceil} floor}) += (dp_{i,j})

容易注意到这样(i-1)至多有(sqrt{a_i})个状态，所以这个状态转移实际上是(O(sqrt{a_i}))的

于是复杂度就是(O(nsqrt{a_i}))

考虑(dp)的贡献就是让前(i)个数连接进来，于是对于状态(i,j)有(ans += dp_{i,j}*(cnt-1) * i)

代码

#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define all(x) x.begin(),x.end()
 
using namespace std;
typedef long long ll;
typedef vector<int>VI;
inline ll rd(){
    ll x;
    scanf("%lld",&x);
    return x;
}
 
const int MOD = 998244353;
 
inline void add(int &a,int b){
    a += b;
    if(a >= MOD) a -= MOD;
}
 
inline int mul(int a,int b){
    return (ll)a * b % MOD;
}
 
inline int ksm(int a,int b = MOD - 2,int m = MOD){
    int ans = 1;
    int base = a;
    while(b){
        if(b & 1) ans = mul(ans,base);
        base = mul(base,base);
        b >>= 1;
    }
    return ans;
}

const int maxn = 1e5 +  5;

int dp[2][maxn];

void solve(){
    int n = rd();
    VI a(n + 1);
    VI v[2];
    for(int i = 1;i <= n;i++)
        a[i] = rd();
    int ans = 0;
    for(int i = n;i >= 1;i--){
        int k = i & 1;
        v[k].push_back(a[i]);
        dp[k][a[i]] = 1;
        int lst = a[i];
        for(auto it:v[k ^ 1]) {
            int y = dp[k ^ 1][it];
            int cnt = (a[i] + it - 1) / it;
            add(dp[k][a[i] / cnt],y);
            add(ans,mul(y,mul(i,cnt - 1)));
            if(lst != a[i] / cnt) {
                v[k].push_back(a[i] / cnt);
                lst = a[i] / cnt;
            }
        }
        for(auto it:v[k ^ 1] ) dp[k ^ 1][it] = 0;
        v[k ^ 1].clear();
    }
    for(auto it:v[0]) dp[0][it] = 0;
    for(auto it:v[1]) dp[1][it] = 0;
    printf("%d
",ans);
}

int main(){
    int T = rd();
    while(T--)
        solve();
}