TREELINE - VOI 2011 Hàng cây
Tác giả: ladpro98
Ngôn ngữ: C++
#include <bits/stdc++.h>
const int N = 222005;
const int B = 1000000000;
using namespace std;
int n, h, lp, Prime[N], Power[N], a[N];
bool isPrime[N];
void initSieve() {
int m = 2*(n+5), i, j;
for(i=2; i<=m; i++)
isPrime[i] = true;
for(i=2; i<=m; i++)
if (isPrime[i]) {
j = i + i;
while (j <= m) {
isPrime[j] = false;
j += i;
}
}
for(i=2; i<=m; i++)
if (isPrime[i]) {
Prime[++lp] = i;
}
}
void addFactorial(int nn, int mul) {
for(int i=1; i<=lp; i++) {
long long v = Prime[i];
while (v <= nn) {
Power[i] += mul * (nn / v);
v *= Prime[i];
}
}
}
long long powMod(int v, int pw) {
if (pw == 0) return 1;
long long t = powMod(v, pw / 2);
t = (t * t) % B;
if (pw & 1) t = (t*v) % B;
return t;
}
int main()
{
//freopen("TREELINE.in", "r", stdin);
scanf("%d %d\n", &n, &h);
int i, res;
long long day = 1;
for(i=1; i<=n; i++) scanf("%d", &a[i]);
for(i=n-1; i>0; i--)
if (a[i] > a[i+1]) break;
res = n - i + 1;
initSieve();
n++;
addFactorial(2*n, 1);
addFactorial(n+1, -1);
addFactorial(n, -1);
for(i=1; i<=lp; i++)
if (Power[i] > 0)
day = (day * powMod(Prime[i], Power[i])) % B;
printf("%d\n", res);
printf("%lld", day);
return 0;
}