首页 > 其他分享 >dp小专题

dp小专题

时间:2022-09-06 09:22:26浏览次数:86  
标签:专题 const int ll long maxn dp

Atcoder_ABC230F

点击查看代码
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn=2e5+10;

const ll mod=998244353;

ll dp[maxn],pre[maxn];
map<ll,int>mp;
ll a[maxn];

int main(){
    #ifdef lmj_debug
        freopen("1.in","r",stdin);
    #endif
    int n;
    cin>>n;
    for (int i=1;i<=n;i++) scanf("%lld",&a[i]);
    for (int i=1;i<=n;i++) pre[i]=pre[i-1]+a[i];
    dp[1]=1;
    for (int i=1;i<n;i++){
        dp[i+1]=dp[i]*2-dp[mp[pre[i]]];
        dp[i+1]=(dp[i+1]+mod)%mod;

        mp[pre[i]]=i;
    }

    cout<<dp[n]<<endl;
    return 0;
}

标签:专题,const,int,ll,long,maxn,dp
From: https://www.cnblogs.com/lmj01/p/16660583.html

相关文章

  • [Google] LeetCode 2172 Maximum AND Sum of Array 状态压缩DP
    YouaregivenanintegerarraynumsoflengthnandanintegernumSlotssuchthat2*numSlots>=n.TherearenumSlotsslotsnumberedfrom1tonumSlots.You......
  • P5664[CSP-S2019] Emiya 家今天的饭 (dp + 计数)
     P5664[CSP-S2019]Emiya家今天的饭(dp+计数)题目传送门题目大意:给定一个大小为\(n*m\)的表格,其中\(a_{i,j}\)表示用第\(i\)种烹饪方式并且有第\(j\)......
  • 54 | JAVA_UDP编程
    UDP编程和TCP编程相比,UDP编程就简单得多,因为UDP没有创建连接,数据包也是一次收发一个,所以没有流的概念。在Java中使用UDP编程,仍然需要使用Socket,因为应用程序在使用UDP时......
  • DP 优化
    只是DP优化罢了,其他乱七八糟的DP根本不会。全文只是我自己的理解,有逻辑上的错误请指出来qwq斜率优化DP斜率优化的流程是这样的。首先列出DP式子,接着钦定两个在......
  • Warp(DP)
    题意有一个人站在二维平面的原点处。他将会进行\(N\)次传送,每次传送他可以做如下三种移动中的一种:从当前位置\((X,Y)\)移动到\((X+A,Y+B)\)从当前位置\((X,Y)\)移动到......
  • 简单计数题(P1350车的放置 dp)
     题目传送门题目大意:给定一个图,在图中放置棋子,每行每列仅能放置一个,求放置\(k\)个的方案数。题目分析:对于给定图,若对于每个点都从前到后进行放置,难免会出现重复......
  • 牛客dfs专题 NC13594 选择困难症(dfs+剪枝)
    链接:https://ac.nowcoder.com/acm/problem/13594来源:牛客网题目描述有k类物品,每类物品的个数为Ai,每个物品有一个喜欢值Vj,代表小L对这件物品的喜欢程度。小L想知道,有多......
  • 【WPF】wpf怎么绑定多个值,多个控件 绑定多个CommandParameter 命令参数
    最近有不少wpf新手问wpf的命令怎么绑定多个控件,很多人为此绞尽脑汁,网上的答案找了也没找到靠谱的,其实用MultiBinding就可以了。从.net3.0版本开始,就支持MultiBinding关于......
  • 洛谷P1850 [NOIP2016 提高组] 换教室(期望dp)
    #include<bits/stdc++.h>usingnamespacestd;intn,m,v,e;intc[3005],d[3005];intf[305][305];doubledp[3005][3005][2];//dp[i][j][k]表示前i步申请更换了j......
  • dp----状态机模型
    《需求引出》《情况一:》在一般的dp问题中,我们的当前项都是可以由前一项推出的,但是在一些情况下我们要用到前前项的情况,这个时候可以将这个情况当做一个状态表示出来,进......