AtCoder ARC #125 : D - Unique Subsequence

ここまでは普通に解けた。
https://atcoder.jp/contests/arc125/tasks/arc125_d

問題

整数列Aが与えられる。
Aの部分列A'のうち、Aからの取り出し方が一意となるものは何通りか。

解法

f(i): = Aのi要素目以降の部分列のうち、先頭にA[i]を含み、かつ問題の条件を満たす組み合わせ
としてf(i)を後ろから埋めて行こう。
i要素目の次に遷移できる(次の要素として部分列に組み込める)条件は

• i要素目以降で、各値が最初に登場する位置
• ただし、A[i]=A[j]となるi以降の最小のjが存在する場合、j要素目以降は遷移できない(A[i]とA[j]どちらかを部分列に取り込めば、同じ部分列が構成できてしまうため)

なので、「A[i]=A[j]となるi以降の最小のj」を管理しながら、BITを使い区間和を求められるようにしていけばよい。

int N;
int A[202020];
const ll mo=998244353;

int did[202020];
int nex[202020];
ll sum;
ll dp[202020];
ll M[202020];

template<class V, int ME> class BIT_mod {
public:
	V bit[1<<ME];
	BIT_mod(){ZERO(bit);};
	V operator()(int e) {ll s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s%mo;}
	void add(int e,V v) { e++; while(e<=1<<ME) { bit[e-1]+=v; bit[e-1] -= (bit[e-1]>=mo)?mo:0; e+=e&-e;}}
};
BIT_mod<ll,20> bt;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	FOR(i,N+1) nex[i]=N+1;
	
	
	
	sum=0;
	for(i=N-1;i>=0;i--) {
		if(nex[A[i]]==N+1) {
			dp[i]=bt(N)+1;
		}
		else {
			dp[i]=bt(nex[A[i]]);
			bt.add(nex[A[i]],mo-dp[nex[A[i]]]);
		}
		nex[A[i]]=i;
		bt.add(i,dp[i]);
	}
	
	cout<<bt(N+1)<<endl;
}

まとめ

これシンプルな問題設定だし、どこかで出てたりしないかな。