脚本宝典收集整理的这篇文章主要介绍了E. Extreme Extension 题解(dp)，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

题目链接

题目思路

这个题目太阴间了

首先要明白对于一个数组，其实拆分的方式是唯一的就是贪心的去搞

然后再根据性质来(dp)

太多细节了，建议看官方题解

ans+=1ll*dp[now^1][x]*(spite-1)*i;

它还需要乘以(i)，因为有(i)个这个，感觉说不清楚...

代码

#include<bits/stdc++.h>
#define fi first
#define se second
#define debug cout<<"I AM HERE"<<endl;
using namespace std;
typedef long long ll;
const int maxn=2e5+5,inf=0x3f3f3f3f,mod= 998244353;
const double eps=1e-6;
int n;
int a[maxn];
vector<int> v[2];
ll dp[2][maxn];
bool vis[maxn];
signed main(){
    int _;scanf("%d",&_);
    while(_--){
        for (auto x: v[0]) vis[x]=dp[0][x] = 0;
        for (auto x: v[1]) vis[x]=dp[1][x] = 0;
        v[0].clear(); v[1].clear();
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
        }
        ll ans=0;
        for(int i=n;i>=1;i--){
            int now=(i&1);
            dp[now][a[i]]=1;
            v[now].push_back(a[i]);
            vis[a[i]]=1;
            for(auto x:v[now^1]){
                int spite=(a[i]+x-1)/x;
                int val=a[i]/spite;
                ans+=1ll*dp[now^1][x]*(spite-1)*i;
                ans%=mod;
                dp[now][val]+=dp[now^1][x];
                dp[now][val]%=mod;
                if(vis[val]) continue;
                vis[val]=1;
                v[now].push_back(val);
            }
            for(auto x:v[now^1]){
                dp[now^1][x]=0;
            }
            v[now^1].clear();
            for(auto x:v[now]){
                vis[x]=0;
            }
        }
        printf("%lldn",ans);
    }
    return 0;
}

脚本宝典总结

以上是脚本宝典为你收集整理的E. Extreme Extension 题解(dp)全部内容，希望文章能够帮你解决E. Extreme Extension 题解(dp)所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。