power sum （累乗和）
(utilities/pow_sum.hpp)

• View this file on GitHub
• Last update: 2021-08-01 20:22:45+09:00
• Include: #include "utilities/pow_sum.hpp"

繰り返し二乗法で $(x^n, \sum_{i=0}^{n-1} x^i)$ の組を計算．計算量は $O(\log n)$．

問題例

• AtCoder Beginner Contest 212 H - Nim Counting

Verified with

• utilities/test/pow.test.cpp

Code

#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};
}

Back to top page