【计数DP】ABC230 F - Predilection

逃离我推掉我的手 2024-03-22 15:08 60阅读 0赞

**计数DP，会不了一点....**

[F - Predilection (atcoder.jp)][F - Predilection _atcoder.jp]

![c66088bd44e64e9287bc7dc279422f5d.png][]

![14dcd4e2e37447b88360bdac3b6e617f.png][]

思路：

![bb469f5ea89c42f684dce555d549cabc.png][]

Code：

#include <bits/stdc++.h>
    
    #define int long long
    #define max(a,b) (a>b?a:b)
    #define min(a,b) (a<b?a:b)
    
    using namespace std;
    
    const int mxn=2e5+10;
    const int mxe=2e5+10;
    const int mod=998244353;
    
    map<int,int> mp;
    
    int N,sum=0;
    int a[mxn],dp[mxn];
    
    void solve(){
    	cin>>N;
    	for(int i=1;i<=N;i++) cin>>a[i];
    	int res=1ll;
    	for(int i=1;i<=N;i++){
    		sum+=a[i];
    		dp[i]=res;
    		res=(res*2ll)%mod;
    		res=((res-dp[mp[sum]])%mod+mod)%mod;
    		mp[sum]=i;
    	}
    	cout<<dp[N]<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[F - Predilection _atcoder.jp]: https://atcoder.jp/contests/abc230/tasks/abc230_f
[c66088bd44e64e9287bc7dc279422f5d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/c0ef2593f5a94249bd55eda041278936.png
[14dcd4e2e37447b88360bdac3b6e617f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/1c5968c2fff8429badda3e5948322fc6.png
[bb469f5ea89c42f684dce555d549cabc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/4d48d80e464042ecbd338b137f76036e.png

发表评论取消回复

表情：

评论列表（有 0 条评论，60人围观）

还没有评论，来说两句吧...

相关阅读

相关【计数DP】ABC230 F - Predilection

计数DP，会不了一点.... [F - Predilection (atcoder.jp)][F - Predilection _atcoder.jp] ![c66088b

逃离我推掉我的手/ 2024年03月22日 15:08/ 0 赞/ 61 阅读

相关（典题）线段计数 CF690 div3 F

[Problem - F - Codeforces][] 题意： ![3b4f0196ed1b4457904652cdf584dd08.png][] ![5d7f4dbb

迈不过友情╰/ 2024年03月03日 00:45/ 0 赞/ 40 阅读

相关 vp230引脚功能_正点原子阿波罗STM32F767

一、硬件整体介绍 1. 底板 ![Image 1][] 底板布局功能图 1.1 CAN总线接口: 采用的是TJA1050CAN总线芯片，在CAN通信

た入场券/ 2023年01月08日 15:28/ 0 赞/ 175 阅读

相关 230-Linux的守护进程

Linux的守护进程守护进程（精灵进程）：运行周期长，一般在后台运行，不需要和用户进行交互。它有点像Windows上的称为服务的进程。比如说画图板，QQ我们打开就看

古城微笑少年丶/ 2022年10月22日 12:00/ 0 赞/ 30 阅读

相关 230.动态单页登录+注册

效果 (源码网盘地址在最后) ![62e4e28a85ea1140a32de0080fd6780b.gif][] 源码 index.html <html

深藏阁楼爱情的钟/ 2022年08月28日 15:54/ 0 赞/ 153 阅读

相关 UVA 230 Borrowers（多种STL运用）

详细题目：https://vjudge.net/problem/UVA-230 思路：根据题意先对各本书进行排序（按ASCII码先作者后书名），建立一个结构体 book

水深无声/ 2022年06月07日 02:58/ 0 赞/ 127 阅读

相关计数

题目描述统计数组 arr 中值等于 item 的元素出现的次数示例1 输入 [1, 2, 4, 4, 3, 4, 3], 4 输出

桃扇骨/ 2022年06月05日 06:41/ 0 赞/ 226 阅读

相关 CodeForces 230A Dragons

题目衔接：[http://codeforces.com/problemset/problem/230/A][http_codeforces.com_problemset_pro

你的名字/ 2022年02月22日 16:10/ 0 赞/ 166 阅读

相关 CodeForces 230B T-primes

题目衔接：[http://codeforces.com/problemset/problem/230/B][http_codeforces.com_problemset_pro

淩亂°似流年/ 2022年02月21日 14:51/ 0 赞/ 120 阅读

相关计数排序

计数排序：假设n个输入元素中的每一个都是在0~区间内的一个整数，其中k为某个整数。当k=O(n)是，排序时间为O（n）. 基本思想：对每个输入元素x,确定小于x元素的

淡淡的烟草味﹌/ 2021年09月23日 03:22/ 0 赞/ 399 阅读