This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub hitonanode/cplib-cpp
#include "utilities/pow_sum.hpp"
繰り返し二乗法で $(x^n, \sum_{i=0}^{n-1} x^i)$ の組を計算.計算量は $O(\log n)$.
#pragma once #include <algorithm> #include <utility> // CUT begin // {x^n, x^0 + ... + x^(n - 1)} for n >= 1 // Verify: ABC212H template <typename T, typename Int> std::pair<T, T> pow_sum(T x, Int n) { T sum = 1, p = x; // ans = x^0 + ... + x^(len - 1), p = x^len for (int d = std::__lg(n) - 1; d >= 0; d--) { sum = sum * (p + 1); p *= p; if ((n >> d) & 1) { sum += p; p *= x; } } return {p, sum}; }
#line 2 "utilities/pow_sum.hpp" #include <algorithm> #include <utility> // CUT begin // {x^n, x^0 + ... + x^(n - 1)} for n >= 1 // Verify: ABC212H template <typename T, typename Int> std::pair<T, T> pow_sum(T x, Int n) { T sum = 1, p = x; // ans = x^0 + ... + x^(len - 1), p = x^len for (int d = std::__lg(n) - 1; d >= 0; d--) { sum = sum * (p + 1); p *= p; if ((n >> d) & 1) { sum += p; p *= x; } } return {p, sum}; }