A. Se puede resolver mediante búsqueda binaria. B. Se define fi como el número esperado de pasos para llegar a la siguiente posición. Una forma de calcularlo es: fi = 1 + (1-p) * (1 + fi-1) + (1-p)^2 * (1 + fi-1) + ... Esta expresión se simplifica a: fi = 1 + ((1-p)/p) * (fi+1) Otra forma es: fi = 1 + (1-p) * (1 + fi-1 + fi) Al resolver esta ecuación, se obtiene el mismo resultado. C. Las secuencias aritméticas son fáciles de manejar, mientras que las geométricas pueden ser resueltas sumando directamente los primeros términos. Para las secuencias de Fibonacci, se calculan los primeros términos y se usan para obtener los restentes mediante recursión.
T1``` #include<bits/stdc++.h> using namesapce std; typedef long long ll; const ll INF = 0x3f3f3f3f3f3f3f3f; const int N = 1e5+10; struct item{ ll start, end; bool operator <(const item& rhs)const{ return make_tuple(start, -end) < make_tuple(rhs.start, -rhs.end); } }it[N], arr[N]; int n, m; bool verify(ll mid){ ll current = arr[1].start; ll index = 1; for(int i = 2; i <= n; ++i){ if(arr[index].end >= current + mid){ current += mid; }else{ do{ ++index; if(index > m) return false; if(current + mid <= arr[index].start) { current = arr[index].start; break; }else{ if(current + mid <= arr[index].end){ current += mid; break; } } }while(1); } } return true; } int main(){ ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); cin >> n >> m; ll low = INF, high = -INF; for(int i = 1; i <= m; ++i){ ll a, b; cin >> a >>b; it[i] = {a, b}; } sort(it + 1, it + 1 + m); int total = 0; arr[++total] = it[1]; for(int i = 2; i <= m; ++i){ if(arr[total].end >= it[i].end) continue; arr[++total] = it[i]; } m = total; for(int i = 1; i < m; ++i){ if(arr[i].end > arr[i + 1].start) arr[i].end = arr[i + 1].start - 1; } ll left = 0, right = 1e18, result = 0; while(left <= right){ ll mid = (left + right) >> 1; if(verify(mid)){ result = mid; left = mid + 1; }else{ right = mid - 1; } } cout << result << endl; return 0; }
T2```
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9+7;
const int N = 5e5+10;
ll power(ll a, ll b){
ll res = 1;
for(;b;b>>=1){
if(b & 1) res = res * a % MOD;
a = a * a % MOD;
}
return res;
}
ll inverse(ll x){
return power(x, MOD-2);
}
ll f[N];
void solve(){
ll p, k;
cin >> k;
ll n = 0;
for(int i = 1; i <= k; ++i){
int x; cin >> x; n += x - 1;
}
cin >> p;
ll base = (1 - p) * inverse(p)%MOD;
base = (base+MOD)%MOD;
f[1] = 1;
for(int i = 2; i <= n; ++i){
f[i] = (1 + base * (1 + f[i-1])%MOD) % MOD;
}
ll ans = 0;
for(int i = 1; i <= n; ++i){
ans = (ans + f[i])% MOD;
}
cout << (ans + MOD)%MOD<< endl;
}
int main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int T;
cin >> T;
while(T--){
solve();
}
return 0;
}
T3``` #pragma GCC optimize(3) #include<bits/stdc++.h> using namespace std; typedef long long ll; const ll MOD = 19260817; const int N = 1e5+10, maxS = 350, maxB = 350, TR = 4 * N, L = N ; ll power(ll a, ll b){ ll res = 1; for(;b;b>>=1){ if(b & 1) res = res * a % MOD; a = a * a % MOD; } return res; } ll inverse(ll x){ return power(x, MOD-2); } ll inv2 = inverse(2); ll fac[L], ifac[L]; void init_fact(int len){ ifac[0] = fac[0] = 1; for(int i = 1; i <= len; ++i) fac[i] = fac[i-1] * i % MOD; ifac[len] = inverse(fac[len]); for(int i = len-1; i >= 1;--i)ifac[i] = ifac[i + 1] * (i + 1 ) % MOD; for(int i = 1; i <= len; ++i) ifac[i] = ifac[i] * fac[i-1]% MOD; } ll sum_1(ll k, ll d, int x){ assert(x >= 1); return (k + d * (x - 1) + k)%MOD * x%MOD * inv2 % MOD; } ll sum_2(ll k, ll d, int x){ return k * (power(d, x) - 1) % MOD * ifac[d-1] % MOD; } struct t_seq1{ struct node{ ll sum; ll k, d; }tree[TR]; void update(int rt, int l, int r, ll k, ll d){ tree[rt].sum = (tree[rt].sum + sum_1(k, d, r - l + 1)) % MOD; tree[rt].k = (tree[rt].k + k) % MOD; tree[rt].d = (tree[rt].d + d) % MOD; } void push_down(int rt, int l, int r){ int mid = (l + r) >> 1; if(tree[rt].k || tree[rt].d){ update(rt<<1, l, mid, tree[rt].k, tree[rt].d); update(rt<<1|1, mid + 1, r, (tree[rt].k + (mid - l + 1 ) * tree[rt].d%MOD) % MOD, tree[rt].d); tree[rt].k = tree[rt].d = 0; } } void push_up(int rt){ tree[rt].sum = (tree[rt<<1].sum + tree[rt<<1|1].sum) % MOD; } void modify(int rt, int l, int r, int s, int t, ll k, ll d){ if(s <= l && r <= t){ update(rt, l, r, (k + (l - s) * d) % MOD,d); return; } int mid = (l + r) >> 1; push_down(rt, l, r); if(s <= mid) modify(rt<<1, l, mid, s, t, k, d); if(t > mid) modify(rt<<1|1, mid + 1, r, s, t, k, d); push_up(rt); } ll query(int rt, int l, int r, int s, int t){ if(s <= l && r <= t){ return tree[rt].sum; } push_down(rt, l, r); int mid = (l + r) >> 1; ll ret = 0; if(s <= mid) ret = query(rt<<1, l, mid, s, t); if(t > mid) ret = (ret + query(rt<<1|1, mid + 1, r ,s, t))%MOD; return ret; } void print(int rt, int l, int r){ cerr<<rt<<" " << l <<" " << r <<" " << tree[rt].sum <<" " << tree[rt].k <<" " <<tree[rt].d << endl; if(l >= r) return; int mid = (l + r) >> 1; print(rt<<1, l, mid); print(rt<<1|1, mid + 1, r); } }seq1; int n, q; ll d; struct t_seq2{ int bel[N]; int S, B, base; ll cnt[maxB]; ll sum[maxB]; int L[maxB], R[maxB]; ll a[N]; void setup(){ S = ceil(sqrt(n)), B = ceil(1.0 * n / S); for(int i = 1; i <= n; ++i) bel[i] = ceil(1.0 * i / S); for(int i = 1; i <= B; ++i) L[i] = R[i-1] + 1, R[i] = i * S; R[B] = n; base = power(d, S); } void update(int l, int r, ll k){ if(bel[l] == bel[r]){ for(int i = l ; i <= r; ++i){ a[i] = (a[i] + k) % MOD; sum[bel[i]] = (sum[bel[i]] + k) % MOD; k = (k * d) % MOD; } return; } for(int i = l, b = bel[i]; i <= R[b]; ++i){ a[i] = (a[i] + k) % MOD; sum[b] = (sum[b] + k) % MOD; k = (k * d) % MOD; } for(int i = bel[l] + 1; i <= bel[r] - 1; ++i){ cnt[i] = (cnt[i] + k) % MOD; sum[i] = (sum[i] + sum_2(k, d, S)) % MOD; k = (k * base) %MOD; } for(int i = L[bel[r]], b = bel[r]; i <= r; ++i){ a[i] = (a[i] + k) % MOD; sum[b] = (sum[b] + k) % MOD; k = (k * d) % MOD; } } void push(int x){ if(cnt[x] == 0) return; for(int i = L[x]; i <= R[x]; ++i){ a[i] = (a[i] + cnt[x]) % MOD; cnt[x] = (cnt[x] * d) % MOD; } cnt[x] = 0; } ll get(int l, int r){ ll res =0; if(bel[l] == bel[r]){ push(bel[l]); for(int i = l; i <= r; ++i){ res = (res + a[i]) % MOD; } return res; } push(bel[l]); push(bel[r]); for(int i = l ; i <= R[bel[l]]; ++i){ res = (res + a[i]); } res %=MOD; for(int i = L[bel[r]]; i <= r; ++i){ res = (res + a[i]); } res %= MOD; for(int i = bel[l] + 1; i <= bel[r] - 1; ++i){ res = (res + sum[i]); } res %= MOD; return res; } }seq2; struct t_seq3{ ll fib[N], fsum[N]; ll a[N]; ll sum[maxB]; ll cnt1[maxB], cnt2[maxB]; int S, B; int bel[N], L[maxB], R[maxB]; void setup_db() { S = ceil(sqrt(n)), B = ceil(1.0 * n / S); for(int i = 1; i <= n; ++i) bel[i] = ceil(1.0 * i / S); for(int i = 1; i <= B; ++i) L[i] = R[i-1] + 1, R[i] = i * S; R[B] = n; } void setup(){ setup_db(); fib[1] = fib[2] = 1; for(int i = 3; i <= n; ++i) fib[i] = (fib[i-1] + fib[i-2]) % MOD; for(int i = 1; i <= n; ++i) fsum[i] = (fsum[i-1] + fib[i]) % MOD; } void update(int l, int r){ if(bel[l] == bel[r]){ for(int i = l; i <= r; ++i){ a[i] = (a[i] + fib[i - l + 1]) % MOD; sum[bel[i]] = (sum[bel[i]] + fib[i - l + 1]) % MOD; } return; } int cur = 1; for(int i = l, b = bel[i]; i <= R[bel[l]]; ++i){ a[i] = (a[i] + fib[cur])%MOD; sum[b] = (sum[b] + fib[cur]) % MOD; ++cur; } for(int i = bel[l] + 1; i <= bel[r] - 1;++i){ cnt1[i] = (cnt1[i] + fib[cur]) % MOD; cnt2[i] = (cnt2[i] + fib[cur-1]) % MOD; sum[i] = (sum[i] + (fsum[cur + S - 1] - fsum[cur-1]) % MOD) % MOD; cur = cur + S; } for(int i = L[bel[r]], b = bel[i] ; i <= r; ++i){ a[i] = (a[i] + fib[cur]) % MOD; sum[b] = (sum[b] + fib[cur]) % MOD; ++cur; } } void push(int x){ ll f2 = cnt2[x], f1 = cnt1[x], f3 = (f1 + f2) % MOD; for(int i = L[x]; i <= R[x]; ++i){ a[i] = (a[i] + f1)%MOD; f2 = f1, f1 = f3, f3 = (f1 + f2) % MOD; } cnt1[x] = cnt2[x] = 0; } ll get(int l, int r){ if(bel[l] == bel[r]){ push(bel[l]); ll res = 0; for(int i = l ; i <= r; ++i){ res = (res + a[i]); } res %= MOD; return res; } push(bel[l]), push(bel[r]); ll res = 0; for(int i = l; i <= R[bel[l]]; ++i){ res = (res + a[i]); } res %= MOD; for(int i = L[bel[r]]; i <= r; ++i){ res = (res + a[i]); } res %= MOD; for(int i = bel[l] + 1; i <= bel[r]- 1; ++i){ res = (res + sum[i]); } res %= MOD; return res; } void print(){ for(int i = 1; i <= B;++i){ cerr<<"i = " << i << " sum = " << sum[i] <<endl; cerr<<"lazy = "; cerr<<cnt1[i] <<" " << cnt2[i] << endl; for(int j = L[i]; j <= R[i];++j){ cerr<< a[j] <<" "; } cerr<<endl; } } }seq3; struct t_seq4{ ll sum[N]; ll get(int l, int r){ return (sum[r] - sum[l-1]) % MOD; } void setup(){ for(int i = 1; i <= n; ++i){ sum[i] = (sum[i-1] + sum[i]) % MOD; } } }seq4; int main(){ init_fact(1e5 + 5); ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); cin >> n >> q >> d; for(int i = 1; i <= n; ++i){ cin >> seq4.sum[i]; } seq2.setup(); seq3.setup(); seq4.setup(); for(int i = 1; i <= q; ++i){ int opt, l, r, k, d; cin >> opt >> l >> r; if(opt == 1){ cin >> k >> d; seq1.modify(1, 1, n, l, r, k, d); }else if(opt == 2){ cin >> k; seq2.update(l, r, k); }else if(opt == 3){ seq3.udpate(l, r); }else{ ll ans1 = seq1.query(1 ,1 ,n, l, r), ans2 = seq2.get(l, r), ans3 = seq3.get(l, r), ans4 = seq4.get(l, r); ll ans = (ans1 + ans2 + ans3 + ans4) % MOD; ans = (ans + MOD) % MOD; cout << ans << "\n"; } } return 0; }