TREELINE - VOI 2011 Hàng cây

Tác giả: happyboy99x

Ngôn ngữ: C++

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

const int N = 1e5, V = 2*(N+1), MOD = 1e9;
bool isp[V+1];
int p[V+1], c[V+1], a[N], n, np;

void eratos() {
	memset(isp, -1, sizeof isp);
	isp[0] = isp[1] = false;
	for(int i = 2; i * i <= V; ++i) if(isp[i])
		for(int j = i+i; j <= V; j += i)
			isp[j] = false;
	for(int i = 2; i <= V; ++i) if(isp[i])
		p[np++] = i;
}

void enter() {
	int h; cin >> n >> h;
	for(int i = 0; i < n; ++i) cin >> a[i];
}

void task1() {
	int res = 2, mn = a[n-1];
	for(int i = n-2; i >= 0; --i)
		if(a[i] <= mn) ++res, mn = a[i];
		else break;
	cout << res << '\n';
}

void analysis(int n, bool dec) {
	for(int i = 0; i < np; ++i) {
		long long x = p[i];
		while(x <= n) {
			if(dec) c[i] -= n / x;
			else c[i] += n / x;
			x *= p[i];
		}
	}
}

long long powmod(long long a, long long n) {
	long long res = 1;
	for(; n != 0; n >>= 1) {
		if(n & 1) res = res * a % MOD;
		a = a * a % MOD;
	}
	return res;
}

void task2() {
	++n;
	analysis(2*n, false);
	analysis(n, true);
	analysis(n+1, true);
	long long res = 1;
	for(int i = 0; i < np; ++i)
		res = res * powmod(p[i], c[i]) % MOD;
	cout << res << '\n';
}

int main() {
	ios::sync_with_stdio(false);
	eratos();
	enter();
	task1();
	task2();
	return 0;
}

Download