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;
}

Download