TREELINE - VOI 2011 Hàng cây
Tác giả: RR
Ngôn ngữ: C++
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <deque>
#include <complex>
#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
#define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
#define ll long long
#define F first
#define S second
#define PB push_back
#define MP make_pair
using namespace std;
//Buffer reading
int INP,AM;
#define BUFSIZE (1<<10)
char BUF[BUFSIZE+1], *inp=BUF;
#define GETCHAR(INP) { \
if(!*inp) { \
fread(BUF,1,BUFSIZE,stdin); \
inp=BUF; \
} \
INP=*inp++; \
}
#define DIG(a) (((a)>='0')&&((a)<='9'))
#define GN(j) { \
AM=0;\
GETCHAR(INP); while(!DIG(INP) && INP!='-') GETCHAR(INP);\
if (INP=='-') {AM=1;GETCHAR(INP);} \
j=INP-'0'; GETCHAR(INP); \
while(DIG(INP)){j=10*j+(INP-'0');GETCHAR(INP);} \
if (AM) j=-j;\
}
//End of buffer reading
const double PI = acos(-1.0);
int n, a[1000111];
int nprime, prime[100111];
bool sieve[200111];
const int BASE = 1000000000;
void init() {
FOR(i,2,450)
if (!sieve[i]) {
int j = i*i;
while (j <= 200000) {
sieve[j] = true;
j += i;
}
}
FOR(i,2,200000)
if (!sieve[i]) prime[nprime++] = i;
}
int get(int n, int p) {
if (n < p) return 0;
return n / p + get(n/p, p);
}
ll power(ll x, int k) {
if (!k) return 1;
if (k == 1) return x;
ll mid = power(x, k >> 1);
mid = (mid * mid) % BASE;
if (k & 1) return (x * mid) % BASE;
else return mid;
}
int main() {
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
int tmp;
GN(n); GN(tmp); FOR(i,1,n) GN(a[i]);
int nn = a[n], u = 0;
FORD(i,n-1,1) {
if (a[i] > nn) {
u = i;
break;
}
nn = min(nn, a[i]);
}
printf("%d\n", n-u+1);
init();
n++;
ll res = 1;
ll now = n + 1;
REP(x,nprime) {
int k = get(n<<1, prime[x]) - (get(n,prime[x]) << 1);
while (now % prime[x] == 0) {
now /= prime[x];
k--;
}
res = (res * power(prime[x], k)) % BASE;
}
cout << res << endl;
return 0;
}