当前位置:网站首页>Value series solution report
Value series solution report
2022-07-05 15:25:00 【wch(】
Value series solution report
label : extremum Combinatorial number
source : Cattle from
Their thinking :
According to the topic definition , It is deduced that the value of a monotonic sequence is the absolute value of the difference between the first two ends , Then try to find the extreme point of the sequence first
To facilitate data processing, we use two arrays to count ,
a The array is included in the array after weight removal ( In this way, it is convenient to judge whether it is the extreme point )
b The array counts the number of original numbers
such as 1 3 3 4 4
Array a The values of are 1 3 4
Array b The values of are 1 2 2
Then consider the influence of extreme number and non extreme number on the final answer
For continuous same extremum ( Aforementioned a[3]) We must keep at least one ans * = 2 Of a[3] Time -1
All non extreme points can be retained or not ans * = 2*2
We use fast exponents to reduce complexity
Code implementation :
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 998244353;
const int N = 1e5 + 8;
int a[N],c[N];
ll ksm(ll a, ll b) {
ll ans = 1;
while (b) {
if (b & 1) (ans *= a) %= mod;
(a *= a) %= mod;
b >>= 1;
}
return ans;
}
bool check(int i){
return (a[i] > a[i - 1] && a[i] > a[i + 1]) || (a[i] < a[i - 1] && a[i] < a[i + 1]);
}
int main() {
int t;
cin >> t;
while (t--) {
ll n;
ll ans = 1;
cin >> n;
int na=0,x;
memset(a,0,sizeof(a));
memset(c,0,sizeof(c));
for (int i = 1; i <= n; i++) {
scanf("%d", &x);
if(a[na]==x){
c[na]++;
}
else{
na++;
a[na]=x;
c[na]++;
}
}
int cnt=n;
if(na==1){
(ans *= ksm(2, c[1])-1) %= mod;
cout<<ans<<endl;
continue;
}
else{
(ans *= ksm(2, c[1])-1) %= mod;
(ans *= ksm(2, c[na])-1) %= mod;
cnt -= c[1]+c[na];
}
for (int i = 2; i <= na-1; i++) {
if (check(i)) {
cnt -= c[i];
(ans *= ksm(2, c[i])-1) %= mod;
}
}
(ans *= ksm(2, cnt)) %= mod;
cout << ans << endl;
}
return 0;
}
边栏推荐
- CODING DevSecOps 助力金融企业跑出数字加速度
- OSI 七层模型
- Install PHP extension spoole
- DVWA range clearance tutorial
- Want to ask the big guy, is there any synchronization from Tencent cloud Mysql to other places? Binlog saved by Tencent cloud MySQL on cos
- Dark horse programmer - software testing -10 stage 2-linux and database -44-57 why learn database, description of database classification relational database, description of Navicat operation data, de
- The elimination strategy of redis
- Bugku easy_ nbt
- 漫画:程序员不是修电脑的!
- I include of spring and Autumn
猜你喜欢
随机推荐
easyOCR 字符识别
把 ”中台“ 的思想迁移到代码中去
First PR notes
keep-alive
Bugku's Eval
Can I pass the PMP Exam in 20 days?
Thymeleaf uses background custom tool classes to process text
sql server char nchar varchar和nvarchar的区别
sql server学习笔记
ICML 2022 | explore the best architecture and training method of language model
Jmeter性能测试:ServerAgent资源监控
Definition of episodic and batch
SQL Server learning notes
I want to inquire about how to ensure data consistency when a MySQL transaction updates multiple tables?
Where is the operation of convertible bond renewal? Is it safer and more reliable to open an account
Au - delà du PARM! La maîtrise de l'Université de Pékin propose diverse pour actualiser complètement le classement du raisonnement du NLP
Magic methods and usage in PHP (PHP interview theory questions)
Bugku's eyes are not real
Go learning ----- relevant knowledge of JWT
Crud de MySQL