はじめに
べき乗大好きです 2問やります
70 NTL_1_B - べき乗
問題はこちらです！
問題文↓
m,nが与えられるので、mⁿを求めてください
繰り返し二乗法をします！
コードはこんな感じです
#include <bits/stdc++.h> #include <chrono> using namespace std; using namespace chrono; #define rep(i, n) for (ll i = 0; i < (n); ++i) #define rep1(i, n) for (ll i = 1; i <= (n); ++i) #define rrep(i, n) for (ll i = n; i > 0; --i) #define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i) #define all(a) (a).begin(), (a).end() #define rall(a) (a).rbegin(), (a).rend() #define yesNo(b) ((b) ? "Yes" : "No") using ll = long long; using ull = unsigned long long; using ld = long double; string alphabet = "abcdefghijklmnopqrstuvwxyz"; string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; const double pi = 3.141592653589793; ll smallMOD = 998244353; ll bigMOD = 1000000007; int dx[] = {1, 0, -1, 0, 1, -1, -1, 1}; int dy[] = {0, 1, 0, -1, 1, 1, -1, -1}; ll repeated_squaring(ll x, ll y, ll z = bigMOD) { ll ans = 1; bitset<64> bits(y); string bit_str = bits.to_string(); reverse(all(bit_str)); rep(i, 64) { if (bit_str[i] == '1') ans = ans * x % z; x = x * x % z; } return ans; } int main() { ll n, m; cin >> n >> m; cout << repeated_squaring(n, m) << endl; return 0; }
repeated_squaring関数をライブラリとして持っておくと強い
71 Square869120Contest #1 E - 散歩
問題はこちらです！
問題文↓
N個の頂点があり、街i-1とiが結ばれているパスグラフがある i-1とiの距離はA[i-1]^A[i]である Q個のクエリが与えられる 初め頂点0からスタートして、0→C[0]→C[1]→...→C[Q-1]→0となるように移動する時、距離の総和を求めてください
まず、全ての頂点間の距離を繰り返し二乗法で求めます
そしたら、クエリを処理するためにLからRまでの区間の和を求めたいです
区間の和といえば累積和なので、累積和テーブルを作成し、O(1)で区間の和を求めます
したがってO(N+Q)で求めることができました
コードはこんな感じです
#include <bits/stdc++.h> #include <chrono> using namespace std; using namespace chrono; #define rep(i, n) for (ll i = 0; i < (n); ++i) #define rep1(i, n) for (ll i = 1; i <= (n); ++i) #define rrep(i, n) for (ll i = n; i > 0; --i) #define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i) #define all(a) (a).begin(), (a).end() #define rall(a) (a).rbegin(), (a).rend() #define yesNo(b) ((b) ? "Yes" : "No") using ll = long long; using ull = unsigned long long; using ld = long double; string alphabet = "abcdefghijklmnopqrstuvwxyz"; string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; const double pi = 3.141592653589793; ll smallMOD = 998244353; ll bigMOD = 1000000007; int dx[] = {1, 0, -1, 0, 1, -1, -1, 1}; int dy[] = {0, 1, 0, -1, 1, 1, -1, -1}; ll repeated_squaring(ll x, ll y, ll z = bigMOD) { ll ans = 1; bitset<64> bits(y); string bit_str = bits.to_string(); reverse(all(bit_str)); rep(i, 64) { if (bit_str[i] == '1') ans = ans * x % z; x = x * x % z; } return ans; } int main() { ll n, q; cin >> n >> q; vector<ll> a(n); rep(i, n) cin >> a[i]; // 距離を計算. vector<ll> dist(n - 1); rep(i, n - 1) { dist[i] = repeated_squaring(a[i], a[i + 1]); } // 区間の和といえば累積和. vector<ll> sum(n); sum[0] = 0; rep(i, n - 1) { sum[i + 1] = sum[i] + dist[i]; } // クエリ処理. ll now = 0; ll ans = 0; rep(i, q) { ll go; cin >> go; ans += abs(sum[go - 1] - sum[now]); ans %= bigMOD; now = go - 1; } ans += abs(sum[0] - sum[now]); ans %= bigMOD; cout << ans << endl; return 0; }
LとRは大きさが逆になることもあるので注意(ここでは絶対値を取りました)
おわり
べき乗マスターになりましたー
ではまた！
、、、区間DPは知らない子です(いつかやります)
