Editorial for VOI 11 Bài 3 - Hàng cây
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của flashmt
#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; }
Code mẫu của happyboy99x
#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; }
Code mẫu của ladpro98
#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; }
Code mẫu của RR
#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; }
Code mẫu của hieult
#include <set> #include <map> #include <list> #include <cmath> #include <queue> #include <stack> #include <cstdio> #include <string> #include <vector> #include <cstdlib> #include <cstring> #include <sstream> #include <iomanip> #include <iostream> #include <algorithm> #include <ctime> #include <deque> #include <bitset> #include <cctype> #include <utility> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned int ui; typedef unsigned long long ull; #define Rep(i,n) for(int i = 0; i < (n); ++i) #define Repd(i,n) for(int i = (n)-1; i >= 0; --i) #define For(i,a,b) for(int i = (a); i <= (b); ++i) #define Ford(i,a,b) for(int i = (a); i >= (b); --i) #define Fit(i,v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i) #define Fitd(i,v) for(__typeof((v).rbegin()) i = (v).rbegin(); i != (v).rend(); ++i) #define mp make_pair #define pb push_back #define fi first #define se second #define sz(a) ((int)(a).size()) #define all(a) (a).begin(), (a).end() #define ms(a,x) memset(a, x, sizeof(a)) template<class F, class T> T convert(F a, int p = -1) { stringstream ss; if (p >= 0) ss << fixed << setprecision(p); ss << a; T r; ss >> r; return r; } template<class T> T gcd(T a, T b) { T r; while (b != 0) { r = a % b; a = b; b = r; } return a; } template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; } template<class T> T sqr(T x) { return x * x; } template<class T> T cube(T x) { return x * x * x; } template<class T> int getbit(T s, int i) { return (s >> i) & 1; } template<class T> T onbit(T s, int i) { return s | (T(1) << i); } template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); } template<class T> int cntbit(T s) { return s == 0 ? 0 : cntbit(s >> 1) + (s & 1); } const int bfsz = 1 << 16; char bf[bfsz + 5]; int rsz = 0; int ptr = 0; char gc() { if (rsz <= 0) { ptr = 0; rsz = (int) fread(bf, 1, bfsz, stdin); if (rsz <= 0) return EOF; } --rsz; return bf[ptr++]; } void ga(char &c) { c = EOF; while (!isalpha(c)) c = gc(); } int gs(char s[]) { int l = 0; char c = gc(); while (isspace(c)) c = gc(); while (c != EOF && !isspace(c)) { s[l++] = c; c = gc(); } s[l] = '\0'; return l; } template<class T> bool gi(T &v) { v = 0; char c = gc(); while (c != EOF && c != '-' && !isdigit(c)) c = gc(); if (c == EOF) return false; bool neg = c == '-'; if (neg) c = gc(); while (isdigit(c)) { v = v * 10 + c - '0'; c = gc(); } if (neg) v = -v; return true; } typedef pair<int, int> II; const ld PI = acos(-1.0); const ld eps = 1e-12; const int dr[] = { -1, 0, +1, 0}; const int dc[] = { 0, +1, 0, -1}; const int inf = (int) 1e9 + 5; const ll linf = (ll) 1e16 + 5; const int mod = (ll) (1e9 + eps); using namespace std; template<int MAXP> struct BitSieve { #define isOn(x) ( p[x >> 6] & ( 1 << ( (x & 63) >> 1) ) ) #define turnOn(x) ( p[x >> 6] |= ( 1 << ( (x & 63) >> 1 ) ) ) int p[(MAXP >> 6) + 1]; BitSieve() { for (int i = 3; i * i <= MAXP; i += 2) { if (!isOn(i)) { int ii = i * i, i2 = i << 1; for (int j = ii; j <= MAXP; j += i2) turnOn(j); } } } bool operator [] (const int x) { return x > 1 && (x == 2 || ( (x & 1) && !isOn(x) ) ); } }; int n,x,a[100002],m,b[100002]; BitSieve<200005> B; int GCD (int a,int b) { int r; while(b!=0) { r = a%b; a = b; b = r; } return a; } int cal(int x, int k){ int res = 0; while(x){ x /= k; res += x; } return res; } int main() { // freopen("in.txt", "r", stdin); long long KQ = 1; scanf("%d %d",&n,&x); for(int i = 1;i<=n;i++) scanf("%d",&a[i]); int chay ; if(n!=0) chay = n-1; else chay = 0; while(chay>0) { if(a[chay]<a[chay+1]) chay--; else break; } printf("%d\n",n-chay+1); n++; int num; For(i, 2, n + n) if(B[i]){ num = cal(n + n, i) - cal(n + 1, i) - cal(n, i); Rep(run, num) KQ = KQ * i % mod; } cout << KQ; //getch(); }
Code mẫu của ll931110
#include <algorithm> #include <bitset> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <deque> #include <fstream> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <utility> #include <vector> using namespace std; int n,h,a[100010]; int module = 1000000000,phi = module / 10 * 4; long long ret = 1,p2 = 0,p5 = 0; long long power(int x,int p,int mod) { if (!p) return 1; long long q = power(x,p/2,mod); q = (q * q) % mod; if (p & 1) q = (q * x) % mod; return q; } void multiply(int x) { while (x % 2 == 0) { p2++; x /= 2; } while (x % 5 == 0) { p5++; x /= 5; } ret = (1LL * ret * x) % module; } void divide(int x) { while (x % 2 == 0) { p2--; x /= 2; } while (x % 5 == 0) { p5--; x /= 5; } ret = (1LL * ret * power(x,phi - 1,module)) % module; } int main() { // freopen("TREELINE.INP","r",stdin); // freopen("TREELINE.OUT","w",stdout); scanf("%d %d", &n, &h); for (int i = 0; i < n; i++) scanf("%d", &a[i]); int way = n + 1,minh = a[n - 1]; for (int i = n - 2; i >= 0; i--) if (a[i] > minh) { way = n - i; break; } else minh = a[i]; printf("%d\n", way); n++; for (int i = n + 2; i <= 2 * n; i++) multiply(i); for (int i = 1; i <= n; i++) divide(i); while (p2--) ret = (ret * 2LL) % module; while (p5--) ret = (ret * 5LL) % module; cout << ret << endl; }
Comments