Solost - 快速幂
type: channel
link: https://solost.cn/tag/%E5%BF%AB%E9%80%9F%E5%B9%82/
items: “范式杯”2023牛客暑期多校训练营1 - J - Roulette
items: AtCoder Beginner Contest 293 - E - Geometric Progression
items: 2023牛客寒假算法基础集训营3 G-严肃古板的秩序

“范式杯”2023牛客暑期多校训练营1 - J - Roulette
type: item
date: 2023-07-18T17:03:06+08:00
description: 题目链接题目链接题目大意有n元钱，要赚到m元。规则是第一局压1元，输了压之前压的2倍，否则继续压1元，输赢的概率都是0.5，问赢到m元的概率是多少题解以“输输输……输赢”为一个周期，可以赢到一块钱。因而需要经过 m 个这样的周期，有x元可以输，赚1块的次数是2^n - 1 <= x，n就是次数。然后我们一共有[n, n + m - 1]可以输，那么输x元赚1元的概率就是1-2^n，由于m很大，有一段区间内的概率是相等的，[2^n - 1, 2^(n + 1) - 2]是相等的，所以我们就可以一次算多个区间的概率代码#include <algorithm> #include <bitset> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <fstream> #include <iostream> #include #include <queue> #include <set> #include <stack> #include <unordered_map> #include <unordered_set> #include <vector> #define x first #define y second #define endl '\n' #define IOS \ ios_base::sync_with_stdio(0); \ cin.tie(0); \ cout.tie(0); using namespace std; typedef long long ll; typedef pair<ll, ll> pll; typedef pair<int, int> pii; typedef unsigned long long ull; const int INF = 0x3f3f3f3f, mod = 998244353; const int N = 2e5 + 10; ll qmi(ll n, ll k, ll p = mod) { ll res = 1 % p; while (k) { if (k & 1) res = res * n % p; n = n * n % p; k >>= 1; } return res; } void solve() { ll n, m; cin >> n >> m; ll ans = 1; for (ll i = 1; (1ll << i) <= n + m; i++) { ll l = max((1ll << i) - 1ll, n), r = min((1ll << (i + 1)) - 2ll, n + m - 1); //从n开始花 if (l > r) continue; ll p = (mod + 1 - qmi((1ll << i), mod - 2)) % mod; ans = ans * qmi(p, r - l + 1) % mod;//r-l+1代表有这么多个概率相同，所以用快速幂相乘 } cout << ans << endl; } int main() { // IOS; int _ = 1; // cin >> _; while (_--) { solve(); } return 0; }

AtCoder Beginner Contest 293 - E - Geometric Progression
type: item
date: 2023-03-16T22:26:27+08:00
description: 题目链接题目链接sloution补充一点点，为什么奇数不能用最后一个公式呢？因为提出A的时候，结果是f(p/2)*xxxx这个需要提出一个式子，所以奇数的时候不能二分，需要用第二个式子来把他再转化成偶数。#include <algorithm> #include <bitset> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <fstream> #include <iostream> #include #include <queue> #include <set> #include <stack> #include <unordered_map> #include <vector> using namespace std; #define x first #define y second #define endl '\n' #define IOS \ ios_base::sync_with_stdio(0); \ cin.tie(0); \ cout.tie(0); typedef long long ll; typedef pair<int, int> PII; typedef unsigned long long ull; const int INF = 0x3f3f3f3f, mod = 1000000007; const int N = 2e5 + 10; ll a, x, m; ll f[N]; ll qmi(ll n, ll k, ll p) { ll res = 1 % p; while (k) { if (k & 1) res = res * n % p; n = n * n % p; k >>= 1; } return res; } ll sum(ll p) { if (p == 0) return 1 % m; if (p % 2) { return (sum(p / 2) % m * (qmi(a, p / 2 + 1, m) + 1) % m) % m; } else { return (a * sum(p - 1) % m + 1) % m; } } void solve() { cin >> a >> x >> m; ll ans = sum(x - 1); cout << ans << endl; } int main() { // IOS; int t = 1; // cin >> t; while (t--) { solve(); } return 0; }

2023牛客寒假算法基础集训营3 G-严肃古板的秩序
type: item
date: 2023-01-21T18:44:00+08:00
description: 这道题的解法是暴力搜索出可能，看三种情况哪种符合，dfs,bfs均可#include <algorithm> #include <bitset> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <fstream> #include <iostream> #include #include <queue> #include <set> #include <stack> #include <unordered_map> #include <vector> using namespace std; #define endl '\n' #define IOS \ ios_base::sync_with_stdio(0); \ cin.tie(0); \ cout.tie(0); typedef long long ll; typedef pair<int, int> PII; typedef unsigned long long ull; const int INF = 0x3f3f3f3f, mod = 1000000007; const int N = 2e5 + 10; ll qmi(ll n, ll k, ll p) { ll res = 1 % p; n = n % p;//注意，虽然每个数字都不可能超过1e9，但是经过累加可能超过int范围， while (k) { if (k & 1) res = 1ll * res * n % p; n = 1ll * n * n % p;//n可能在n * n的时候超过ll范围，所以需要先取余 k >>= 1; } return res; } ll res = 0, cnt = 0, f = 0, b[20]; string ans; struct node { ll first, second;//first是前n项操作后的数字，second是处理了几个数字了 string s;//存放进行的操作 }; void bfs() { queue<node> q; node head; head.first = b[1]; head.second = 1; q.push(head); while (q.size()) { auto t = q.front(); q.pop(); if ((int)t.s.size() >= cnt) continue; for (int i = 0; i < 3; i++) { auto ne = t; if (i == 0) { ne.first += b[ne.second + 1]; ne.second++; ne.s = ne.s + '+'; } else if (i == 1) { ne.first -= b[ne.second + 1]; ne.second++; ne.s = ne.s + '-'; } else if (i == 2) { if (ne.first <= 0 || b[ne.second + 1] <= 0) continue; ne.first = qmi(ne.first, ne.first, b[ne.second + 1]); ne.second++; ne.s = ne.s + '#'; } q.push(ne); if ((int)ne.s.size() == cnt && ne.first == b[res]) { f = 1; ans = ne.s; return; } } } } int main() { ll xx; string s; char op = 'a'; while (cin >> xx) { s = s + to_string(xx); b[++res] = xx; if (op == '=') break; cin >> op; s = s + op; if (op == '?') cnt++; } bfs(); if (!f) { cout << "-1\n"; } else { int j = 0; for (int i = 0; i < (int)s.size(); i++) { if (s[i] == '?') { s[i] = ans[j++]; } } cout << s << endl; } return 0; }