題解

我們可以把問題看成我們要尋找一些不重疊區間，使得各個區間內所有數的集合是互不相同的。

舉例來說，$[1, 2, 1, 2, 3]$，$[1, 2, 1, 2]$跟$[3]$就可以斷開成兩個區間。

所以，我們可以預先記錄每一種數字最後一次出現的位子，搭配上一個set記錄區間內目前看過，且在此位子後面還有再出現的數字有哪些。由左而右，掃過去並且更新。當set為空，就帶表這個區間內所出現的所有數字，在此之後都不再出現了，也就是可以在此下斷點！

至於組合數部分，因為有斷點之處，只能維持現在的數值或是$+1$，所以就是$2$種可能而已。因此答案就是遇到斷點就$*=2$

題外話，這題亂用unordered系列的東西，會超時…

AC Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44


#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

const ll MOD = 998244353;

int main()
{
    int n;
    scanf("%d", &n);

    int inp[n];
    map<int, int> lastPos;
    for (int i = 0; i < n; i++) {
        scanf("%d", &inp[i]);
        lastPos[inp[i]] = i;
    }

    set<int> workingWindow;
    ll ans = 1;
    bool ok = false;
    for (int i = 0; i < n; i++) {
        if (ok)
            ans = ans * 2 % MOD;
        ok = false;
        if (lastPos[inp[i]] == i) {
            workingWindow.erase(inp[i]);

            if (workingWindow.size() == 0) {
                ok = true;
            }
        } else {
            workingWindow.insert(inp[i]);
        }
    }

    printf("%lld\n", ans);

    return 0;
}