Codeforces J. Monotonic Renumeration（组合）

题目描述：

You are given an array consisting of nmonotonic renumeration as an array b consisting of \(n\)integers such that all of the following conditions are met:

b1=0;
for every pair of indices iand jsuch that 1≤i,j≤n, then \(b_i=b_j\), it is still possible that \(b_i=b_j\)

for every index i∈[1,n−1] either \(b_i=b_{i+1}\) or \(b_{i+1}\)=\(b_i\)+1

For example, if a=[1,2,1,2,3], then two possible monotonic renumerations of are b=[0,0,0,0,0]\(b=[0,0,0,0,1]\).

Your task is to calculate the number of different monotonic renumerations of a. The answer may be large, so print it modulo \(998244353\).

Input

The first line contains one integer n(\(2\leq{n}\leq{2*10^5}\)) — the number of elements in a

The second line contains n

integers (\(1≤a_i≤10^9\))

Output

Print one integer — the number of different monotonic renumerations of a, taken modulo 998244353.

Examples

Input

Copy

5

1 2 1 2 3

Output

Copy

Input

Copy

2

100 1

Output

Copy

Input

Copy

4

1 3 3 7

Output

Copy

思路：

题目的意思是给一个数列a，构造数列b，按照以下规则：如果a中有相同的元素，相同元素的位置对应在b中位置上的元素必须也想同。还有b是非减数列，一次最多增加1.

那么我们可以知道a相同元素的位置对应在b的位置，这个位置之间的所有元素在b中必须相同。因为b中元素要么与前一个一样，要么大一。

题目就变成了，找到重合的区间加起来得到总的重合区间，这个总区间上的元素在b中必须相同。

可以在输入时记录下每个元素的最远相同元素的位置，如果没有相同元素就记录本身位置。然后遍历一遍数组，记录当前重合区间的右端点。如果元素位置在当前重合区间右端点内，元素必须相同，没得选，就不断更新重合区间右端点；直到元素位置大于区间右端点，说明已经不在重合区间内，可以选择元素大小了，有两种选法，总结果就乘上2，然后把区间右端点更新为当前位置，继续遍历。注意这个不在区间内本身就可能是新的重合区间，而不只是不在重合区间内的一个点。按照算法乘以二更新右端点后就可以正确继续执行。

代码：

#include <iostream>

#include <map>

#define maxn 200005

#define mod 998244353

using namespace std;

int n;

int a[maxn];

map<int,int> mp;

int main()

{

    cin >> n;

    for(int i = 0;i<n;i++)

    {

        cin >> a[i];

        mp[a[i]] = i;

    }

    int right = 0;//当前区间右端点

    long long ans = 1;

    for(int i = 0;i<n;i++)

    {

        if(i<=right)

        {

            right = max(right,mp[a[i]]);

        }

        else

        {

            ans = (ans*2)%mod;

            right = mp[a[i]];

        }

    }

    cout << ans << endl;

    return 0;

}

巴特西

Codeforces J. Monotonic Renumeration（组合）

题目描述：

思路：

代码：

最新文章

热门文章