ARC125D Unique Subsequence

tony102

2021 年 10 月 30 日

1258 次浏览

暂无评论

606字数

题解

[Link](https://atcoder.jp/contests/arc125/tasks/arc125_d)

## Sol

设 $f_i$ 表示前 $i$ 个数构成了多少个不同的子序列。

转移应该分为两种，一种就是前面都没有出现过这个数字，否则就应该从出现过的位置转移过来。

最开始很 naive 的写了一个转移（被样例 2 误导了），就是认为前面没有一样的就可以直接是 $2^{i-1}$ 随便选，其实这中间可能有别的数字重复出现过就算重了....

真正的转移应该是，假如当前这个位置的数前面出现过了，就在其位置答案清空然后记到上一个出现位置的 $f$ 的和，否则直接 $+1$ 即可。

树状数组做一下就可以了。

## Code

```cpp
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int SIZE = 2e5 + 5;
const LL mod = 998244353;

int n;
int a[SIZE], pre[SIZE]; LL f[SIZE];

namespace GTR {
	const int bufl = 1 << 20;
	char buf[bufl], *s = buf, *t = buf;
	inline int fetch() {
		if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
		return *s++;
	}
	inline int read() {
		int a = 0, b = 1, c = fetch();
		while (c < 48 || c > 57) b ^= c == '-', c = fetch();
		while (c >= 48 && c <= 57) a = a * 10 + c - 48, c = fetch();
		return b ? a : -a;
	}
} using GTR::read;

namespace Bit {
    #define lowbit(x) (x & (-x))
    LL bit[SIZE]; int N;
    void modify(int x, LL v) {
        for ( ; x <= N; x += lowbit(x)) bit[x] = (bit[x] + v) % mod;
    }
    LL query(int x) {
        LL ans = 0;
        for ( ; x; x -= lowbit(x)) ans = (ans + bit[x]) % mod;
        return ans % mod;
    }
    LL query(int l, int r) { return (query(r) - query(l - 1) + mod) % mod; }
} using Bit::modify; using Bit::query;

int main() {
    n = read(); Bit::N = n + 1;
    for (int i = 1; i <= n; ++ i) a[i] = read(), pre[i] = n + 1;
    for (int i = n; i; -- i) {
        f[i] = query(i, pre[a[i]]);
        if (pre[a[i]] == n + 1) f[i] = (f[i] + 1ll) % mod;
        else modify(pre[a[i]], mod - f[pre[a[i]]]);
        modify(i, f[i]), pre[a[i]] = i;
    }
    LL ans = 0;
    for (int i = 1; i <= n; ++ i) {
        if (pre[a[i]] == i) ans = (ans + f[i]) % mod;
    }
    printf("%lld\n", ans);
    return 0;
}
```

最后修改：2021 年 10 月 30 日