赞
踩
E. Monotonic Renumeration
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
You are given an array aa consisting of nn integers. Let's denote monotonic renumeration of array aa as an array bb consisting of nn integers such that all of the following conditions are met:
For example, if a=[1,2,1,2,3]a=[1,2,1,2,3], then two possible monotonic renumerations of aa are b=[0,0,0,0,0]b=[0,0,0,0,0] and b=[0,0,0,0,1]b=[0,0,0,0,1].
Your task is to calculate the number of different monotonic renumerations of aa. The answer may be large, so print it modulo 998244353998244353.
Input
The first line contains one integer nn (2≤n≤2⋅1052≤n≤2⋅105) — the number of elements in aa.
The second line contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1091≤ai≤109).
Output
Print one integer — the number of different monotonic renumerations of aa, taken modulo 998244353998244353.
Examples
input
Copy
5 1 2 1 2 3
output
Copy
2
input
Copy
2 100 1
output
Copy
2
input
Copy
4 1 3 3 7
output
Copy
4
大致题意:
当i = j,a[i] = a[j]时,i---j之间的数相同,若a[i] != a[j],a[j] = a[i] 或 a[j] = a[i] + 1
例如 1 2 1 2 3 则 b 可能为 0 0 0 0 0,或 0 0 0 0 1
1 100 b可能为 0 0 或 0 1
求的是b的方案数
- //此题意是统计方案数
- // 由于当a出现间断点时,b要么不变要么+1
- // 所以每当出现间断点总数就要*2
- # include <iostream>
- # include <algorithm>
- # include <cstring>
- # include <math.h>
- # include <stdio.h>
- # include <vector>
- # include <map>
- using namespace std;
- const int mod = 998244353;
- map<int,int> mmp;//映射
- int main(){
- int n;
- cin >> n;
- int num[200100];
- int f = 0;
- for(int i = 1; i <= n; i++){
- cin >> num[i];
- mmp[num[i]] = i;//统计这个数最后出现的位置
- }
- int flag = 1; //flag 用来统计是否交叉
- int tot = 1; //tot 用来统计总方案数
- for(int i = 1; i <= n; i++){
- if(flag >= i){//出现中断
- flag = max(flag , mmp[num[i]]);//flag推到这个点的最后出现位置
- }
- //因为a[1] 规定为 0,所以它不在间断点
- else{//不在间断点
- tot = tot * 2 % mod;//统计方案数
- flag = max(flag , mmp[num[i]]); // 同理
- }
- }
- cout << tot << endl;
- return 0;
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。