TREELINE - VOI 2011 Hàng cây
Tác giả: flashmt
Ngôn ngữ: C++
#include<iostream>
#include<algorithm>
#define fr(a,b,c) for(a=b;a<=c;a++)
#define frr(a,b,c) for(a=b;a>=c;a--)
#define maxn 100010
#define z 1000000000
using namespace std;
int n,a[maxn],re=2,np,p[maxn],d[maxn*2],f[maxn];
void prime()
{
int i,j;
fr(i,2,500)
if (!d[i])
{
j=i*i;
while (j<=200002)
{
d[j]=1;
j+=i;
}
}
fr(i,2,200002)
if (!d[i]) p[++np]=i;
}
void calc(int n,int y)
{
int i;
fr(i,1,np)
if (p[i]<=n)
{
int x=p[i];
while (x<=n)
{
f[i]+=(n/x)*y;
if (p[i]<500) x*=p[i];
else break;
}
}
else break;
}
int main()
{
int i,j;
cin >> n >> i;
fr(i,1,n) scanf("%d",&a[i]);
frr(i,n-1,1)
if (a[i]<a[i+1]) re++;
else break;
cout << re << endl;
n++;
prime();
calc(n*2,1);
calc(n,-1);
calc(n+1,-1);
long long res=1;
fr(i,1,np)
if (f[i])
fr(j,1,f[i])
res=(res*p[i])%z;
cout << res << endl;
return 0;
}