洛谷 P6146

由于博主是只鸽子，所以咕咕咕。（）
不，应该是目录不在更新，请关注博客首页。
有空我把目录更新一下，好久不更了

传送门

You are Miserable (AT Lv.15)

思路

Stage 1

这题其实是个 DP 。没想到吧？

Stage 2

如果第 $ i $ 条线段不用，那就是 $ f_{i - 1} $ 。
用的话，一部分是 $ f_{i - 1} $ ，另一部分呢？

Stage 3

令 $ sum_i $ 表示在数轴上 $ i $ 之前有多少个右端点。
另一部分：如果之前有 $ x $ 条线段不与第 $ i $ 条线段相交，则这 $ x $ 条线段的一个子集都能交给 $ i $ 来加一，也就是 $ 2^x $ 。
所以，$ f_i = 2f_{i - 1} + 2^x $ 。
最终答案显然是 $ f_n $ 喽。

代码

注意由于 $ 2^x $ 可能会爆 $ ull $ ，所以要用快速幂。

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

#define MOD 1000000007

int f[100005], sum[200005];
pair<int, int> seg[100005];

long long qpow(long long base, long long exp, long long mod) {
	long long ans = 1;
	while (exp) {
		if (exp & 1) {
			ans = (ans * base) % mod;
		}
		exp >>= 1;
		base = (base * base) % mod;
	}
	return ans;
}

int main() {
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d %d", &seg[i].first, &seg[i].second);
	}
	sort(seg + 1, seg + 1 + n);
	for (int i = 1; i <= n; i++) {
		sum[seg[i].second]++; 
	}
	for (int i = 1; i <= 2 * n; i++) {
		sum[i] += sum[i - 1];
	}
	sort(seg, seg + n);
	for (int i = 1; i <= n; i++) {
		f[i] = (f[i - 1] * 2 % MOD + qpow(2, sum[seg[i].first - 1], MOD)) % MOD;
	}
	printf("%d", f[n]);
	return 0;
}