当前位置:网站首页>[count] [combined number] value series
[count] [combined number] value series
2022-07-06 07:39:00 【Code chess】
Topic link :
https://ac.nowcoder.com/acm/contest/23481/B
Don't calculate the sequence a The value of , Because it is difficult to do it from this aspect .
Which values should be taken from the sequence to make the sequence a The value remains unchanged .
For three numbers to discuss :
- a i < a j < a k a_i < a_j <a_k ai<aj<ak or a i > a j > a k a_i >a_j>a_k ai>aj>ak when
Delete the number in the middle , The value of the sequence will not change . If the same number in the middle hask
individual , The number of cases is 2 k 2^k 2k - a i < a j > a k a_i < a_j >a_k ai<aj>ak or a i > a j < a k a_i >a_j<a_k ai>aj<ak when
Delete the middle value , The value of the sequence will change , So you can't delete . But if there are multiple equal values in the middle , Leave at least one value . If the number of equal numbers isk
, Then the number of cases is 2 k − 1 2^k-1 2k−1( Remove the empty condition )
Next , Is to discuss the same number in the middle
Treat equal numbers as a connected block , Set to [ i , j ] [i,j] [i,j]
- If meet a i − 1 < a i = . . . = a j < a j + 1 a_{i-1}<a_i=...=a_j<a_{j+1} ai−1<ai=...=aj<aj+1 or a i − 1 > a i = . . . = a j > a j + 1 a_{i-1}>a_i=...=a_j>a_{j+1} ai−1>ai=...=aj>aj+1( And to satisfy i > 1 , j < n i>1,j<n i>1,j<n), Then interval [ i , j ] [i,j] [i,j] The number of can be deleted completely , Does not affect the value , Such a range contributes a lot to the answer 2 j − i + 1 2^{j-i+1} 2j−i+1 Kind of plan .
- Otherwise, the interval [ i , j ] [i,j] [i,j] The number of must keep one , Such a range contributes to the answer 2 j − i + 1 − 1 2^{j-i+1}-1 2j−i+1−1 Kind of plan . The answer is to multiply the contributions of all intervals .
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 5, mod = 998244353;
vector<ll> fac(N);
void solve()
{
int n;
cin >> n;
vector<int> a(n);
for(auto &i : a) cin >> i;
ll res = 1;
for(int i = 0, j = 0; i < n; i++)
{
j = i;
while(j < n - 1 && a[j + 1] == a[i]) j++;
if(i - 1 >= 0 and j + 1 < n and (a[i - 1] < a[i] && a[i] < a[j + 1] || a[i - 1] > a[i] && a[i] > a[j + 1]))
res = res * fac[j - i + 1] % mod;
else res = res * (fac[j - i + 1] - 1) % mod;
i = j;
}
cout << res << "\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
fac[0] = 1;
for(int i = 1; i < N; i++)
fac[i] = fac[i - 1] * 2 % mod;
int t;
cin >> t;
// t = 1;
while(t--) solve();
return 0;
}
边栏推荐
猜你喜欢
[1. Delphi foundation] 1 Introduction to Delphi Programming
[computer skills]
Ble of Jerry [chapter]
Typescript interface and the use of generics
Generator Foundation
NiO programming introduction
继电反馈PID控制器参数自整定
Opencv learning notes 8 -- answer sheet recognition
How to prevent Association in cross-border e-commerce multi account operations?
珠海金山面试复盘
随机推荐
Games101 Lesson 7 shading 1 Notes
解决方案:智慧工地智能巡检方案视频监控系统
Typescript variable scope
超级浏览器是指纹浏览器吗?怎样选择一款好的超级浏览器?
Memory error during variable parameter overload
The way to learn go (I) the basic introduction of go to the first HelloWorld
TS 类型体操 之 extends,Equal,Alike 使用场景和实现对比
【mysql学习笔记30】锁(非教程)
Jerry's ad series MIDI function description [chapter]
Comparison of usage scenarios and implementations of extensions, equal, and like in TS type Gymnastics
Oracle column to row -- a field is converted to multiple rows according to the specified separator
【Redis】NoSQL数据库和redis简介
http缓存,强制缓存,协商缓存
Force buckle day31
How to prevent Association in cross-border e-commerce multi account operations?
datax自检报错 /datax/plugin/reader/._drdsreader/plugin.json]不存在
[online problem processing] how to kill the corresponding process when the MySQL table deadlock is caused by the code
解决方案:智慧工地智能巡檢方案視頻監控系統
数字IC设计笔试题汇总(一)
onie支持pice硬盘