Codeforces 314C - Sereja and Subsequences

問題文 : Sereja and Subsequences

概要 :

数列${a_n}$ がある. ${a_n}$ の相異なる全ての非減少部分列${b_n}$ について, $b_1b_2\cdots b_n$ を求め, その和をmod $10^9+7$ で求めよ.

$n \leqq 10^5$

解法 :

小さい数から数列を構成していくことを考えると, 自分より前に自分と同じ数が無い時と同じ数があるときで簡単な場合分けをしてDP すれば良いことが分かる. 部分和を高速に求める必要が有るため, BIT を使うと良い.

コード :

#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long lint;

lint bit[100100];

void add(int k, int x)
{
	k += 1;
	while (k <= 100099){
		bit[k] = (bit[k] + x) % 1000000007;
		k += k & -k;
	}
}

lint sum(int k)
{
	k += 1;
	lint ret = 0;
	while (k){
		ret += bit[k];
		ret %= 1000000007;
		k &= (k - 1);
	}
	return (ret);
}

int main()
{
	int N;
	pair<int, int> p[100000];
	
	scanf("%d", &N);
	
	for (int i = 0; i < N; i++){
		int a;
		scanf("%d", &a);
		p[i].first = a; p[i].second = i;
	}
	
	sort(p, p + N);
	
	lint ans = 0;
	
	for (int i = 0; i < N; i++){
		lint x = sum(p[i].second) + 1;
		if (i && p[i].first == p[i - 1].first){
			x = (sum(p[i].second) - sum(p[i - 1].second - 1) + 1000000007) % 1000000007;
		}
		add(p[i].second, (p[i].first * x) % 1000000007);
		ans = (ans + p[i].first * x) % 1000000007;
	}
	
	printf("%lld\n", ans);
	
	return (0);
}