FPS の冪乗の係数列挙 (Power Projection) の亜種
はじめに
Power Projection とは以下の問題のことを指します。
- FPS(形式的冪級数) $f(x), g(x)$ が与えられるので、$i = 0, 1, \dots, n$ について、$[x^{n}]f(x)^{i}g(x)$ を求めてください。
この問題は noshi91 さんによって、$\Theta(n\log(n)^{2})$ で解けることが発見されました。
noshi91 さんによる初出のブログ : FPS の合成と逆関数、冪乗の係数列挙 $\Theta(n\log(n)^{2})$
maspy さんによる実装方針を含めた解説ブログ : FPS 合成・逆関数の解説（１）逆関数と Power Projection
本題
- FPS $f(x), g(x)$ が与えられるので、$i = 0, 1, \dots, n$ について、$[x^{i}]f(x)^{i}g(x)$ を求めてください。
求める係数が $x^{n}$ から $x^{i}$ に変わっています。
解説
$[x^{0}]f(x) = 0$ のときは、$[x^{i}]f(x)^{i}g(x) = ([x^{1}]f(x))^{i}[x^{0}]g(x)$ が成り立つので簡単に求められます。以降、$[x^{0}]f(x) \neq 0$ であるとします。
まず、以下の等式が成り立ちます。
$[x^{i}]f(x)^{i}g(x) = [x^{n}]x^{n - i}f(x)^{i}g(x)$
ここで、$k = n - i$ とします。すると、以下のように変形できます。
$[x^{n}]x^{n - i}f(x)^{i}g(x) = [x^{n}]x^{k}f(x)^{n - k}g(x) = [x^{n}] (xf(x)^{-1})^{k}(f(x)^{n}g(x))$
よって、$k = 0, \dots, n$ に対して、上記の値を求めることができれば元の問題を解くことができます。
$f(x)^{-1}$ と $f(x)^{n}$ の $n$ 次までの値が分かればこの問題は Power Projection と全く同じ形になっているので解くことができるのですが、これらは高速に解けることが知られています。
maspy さんのブログ : 多項式・形式的べき級数-高速に計算できるもの
実装例
AtCoder Library と自分が使っているライブラリを用いて、例えば以下のように書くことができます。
#include "po167_library/fps/FPS_Power_Projection.hpp" #include "po167_library/fps/FPS_pow.hpp" // n := |f(x)| = |g(x)| // return i = 0, 1, ... n - 1 // [x^{i}] g(x) f(x)^{i} // = [x^{n - 1}] f^{n - 1}g (xf^{-1})^{n - 1 - i} template<class T> std::vector<T> power_projection_2(std::vector<T> g, std::vector<T> f){ int n = g.size(); assert((int)f.size() == n); if (n == 0) return {}; std::vector<T> res(n); if (f[0] == 0){ res[0] = g[0]; for (int i = 1; i < n; i++){ res[i] = res[i - 1] * f[1]; } return res; } std::vector<T> G = atcoder::convolution(g, po167::FPS_pow(f, n - 1)); G.resize(n); f = po167::FPS_inv(f); f.pop_back(); f.insert(f.begin(), 0); res = po167::Power_Projection(G, f, n); std::reverse(res.begin(), res.end()); return res; }
出題例
The 4th Universal Cup. Stage 17 F
数列 $A$ が与えられます。$n = 1, 2, \dots, N$ について、以下の条件を全て満たす 01 文字列の場合の数を $998244353$ で割ったあまりを求めてください。
- 長さが $2n$
- 文字列に含まれる 0, 1 の数が等しい
- 末尾に連続する 0 の数を $a$ としたとき、$a$ は数列 $A$ に含まれる
解説
この問題自体は log 1 つで解けるらしいですが、自分はまだ理解できていないので今回は省略します。
1 を境目としてみることで、以下の問題に帰着できます。
- 長さ $n + 1$ の非負数列 $B$ であって、総和が $n$ かつ $B_{n + 1}$ が $A$ に含まれるものは何通りですか。
$f(x) = 1 + x + \cdots = \dfrac{1}{1 - x}$ と置くことで答えは以下のようになります。
$\displaystyle\sum_{a\in A}[x^{n - a}] f(x)^{n}$
$g(x) = \displaystyle\sum_{a\in A} x^{a}$ とすると、答えは $[x^{n}] f(x)^{n} g(x)$ と表せ、Power Projection の亜種に帰着できました。この問題では $f(x)$ の pow や inv は線形で求められますが、計算量には影響しないです。
#include <iostream> #include <atcoder/modint> using mint = atcoder::modint998244353; int main() { int N, M; std::cin >> N >> M; std::vector<mint> A(N + 1); for (int i = 0; i < M; i++){ int a; std::cin >> a; A[a] = 1; } std::vector<mint> B(N + 1, 1); auto ans = power_projection_2(A, B); for (int i = 1; i <= N; i++){ std::cout << ans[i].val() << "\n"; } }
終わり
既に知られた話かも知れませんが、自分は知らなかった/頭に残っていなかったので記事にしました。
これはただの意思表明なのですが、これからは積極的にアウトプットしていきたいと思います。
yukicoder No.3322 引っ張りだこ 解法
はじめに
元の問題では入力で $K$ が与えられますが、任意の $K$ についても同じ計算量で解くことができます。
問題概要
長さ $N$ の整数列 $A, B$ が与えられます。$K = 0, 1, \dots , N - 1$ について以下の問いに答えてください。
長さ $N$ の AB からなる文字列 $S$ のコストとスコアを以下のように定義します。
コスト : 文字列 $T$ を $S$ の先頭に A 追加したものとして、$T$ の異なる文字が隣接している箇所の数
スコア : $i$ 文字目が A なら $A_{i}$ を、B なら $B_{i}$ を $x$ に加算するという操作を $i = 1, 2,\dots , N$ について $x = 0$ から始めたときの最終的な $x$
コストが $K$ 以下であるような文字列 $S$ に対するスコアの最大値を求めてください。
解法
$K$ を固定したときの答えを求めます。
$A, B, K$ について、以下が成り立っているとして良いです。
- $A_{1} = 0, B_{1} = -\inf$
- $A_{N} = -\inf, B_{N} = 0$
- $N$ は偶数
- $K$ は奇数
- $A_{i} < B_{i}$ ならば $A_{i + 1}\geq B_{i + 1}$
- $A_{i} \geq B_{i}$ ならば $A_{i + 1}< B_{i + 1}$
そうでない場合、以下のように置き換えます。
置き換え
コストの定義で $S$ の先頭に A を追加しているのが面倒くさいので、$A, B$ を以下のように置き換えます。
- $A = (0) + A$
- $B = (-\inf) + B$
すると、コストの定義はただ単に $S$ の異なる文字が隣接している箇所になります。
次に、$K$ が偶数なら $A, B$ を以下のように置き換えます。
- $A = A + (0)$
- $B = B + (-\inf)$
これは元 $S$ の末尾が A ならばコストを変えずにスコアを維持できます。そうでなくてもコストを $1$ 増やすだけでスコアを維持できるし、元のコストは $K$ 未満なので、$K$ を超えません。そして、$K + 1$ でも答えが変わらないので、$K$ に $1$ を加算することで $K$ が奇数の場合に帰着できました。
$K$ が奇数のとき、先ほどの理論と同様に、$A, B$ を以下のように置き換えても答えが変わりません。
- $A = A + (-\inf)$
- $B = B + (0)$
また、$A_{i} < B_{i}$ かつ $A_{i + 1} < B_{i + 1}$ なら $A, B$ を以下のように置き換えて良いです。
$A = (A_{1}, \dots , A_{i- 1}) + (A_{i} + A_{i + 1}) + (A_{i + 2}, \dots , A_{N}) $
$B = (B_{1}, \dots , B_{i- 1}) + (B_{i} + B_{i + 1}) + (B_{i + 2}, \dots , B_{N}) $
なぜならある $S$ について、$S_{i} \neq S_{i + 1}$ が成り立っているなら、$S_{i} = S_{i + 1} = $B とすることで、コストを増やすことなくスコアを上げられるからです。
この置き換えは $A_{i} \geq B_{i}$ かつ $A_{i + 1} \geq B_{i + 1}$ が成り立っているときでも行って良いです。
以上のように置き換えると、最初の条件を満たす数列になります。また、スコアの最大値は変わらないことも示せています。
JOI 飴への帰着
文字列 $T$ を AB を $\frac{N}{2}$ 回繰り返したものとします。
$S$ の最適解について、$K\neq 0$ であることから、$S_{1} = $A かつ $S_{N} = $B が成り立ちます。また、以下が成り立っています。
- $T_{i} \neq S_{i}$ かつ $T_{i} \neq S_{i + 1}$ が成り立つ $i$ は存在しない。
これは $S_{i} = S_{i + 1} = $B とすることで、コストを増やすことなくスコアを上げられるからです。
以上より、コストは $S_{i} \neq T_{i}$ が成り立つ $i$ の数の $2$ 倍に $1$ を足したものとして良いです。よって、「$S_{i} \neq T_{i}$ である $i$ の数が与えられるので、$S$ のスコアの最大値を求めてください。」という問題を解けば良いです。
$S_{i} \neq T_{i}$ を満たす $i$ の集合を $U$ としたとき、スコアは以下のように表せます。
- $\sum\max(A_{j}, B_{j}) - \sum_{i\in U} |A_{i} - B_{i}|$
よって、「隣接しないように $i$ を指定された数選び、そのような $i$ に対する $|A_{i} - B_{i}|$ の総和を最小化してください。」という問題に帰着できました。
これはまさしく JOI 飴であるので、同じ解法で解けます。また、指定された数は $0$ 以上 $N - 1$ 以下の任意の数について同時に求められるので、元の問題も任意の $K$ に対する答えが同時に求められます。
JOI 飴の参考文献
解説などもこのリンク先から辿れると思います。
コード
おまけ
コンテスト中は、monge d 辺最短路に帰着して解いていたため、TLE になってしまいました。より難しい問題に帰着して TLE ということを、最適化でよくしてしまうので注意した方がいいかもしれない。
AtCoder Regular Contest 204 作問経緯
AtCoder Regular Contest 204 に参加していただいた皆さんありがとうございました。そうでない方は upsolve していただけるとありがたいです。
これらの文章はコンテスト前に書かれています。コンテスト前の自分の感覚としては比較的簡単なセットだと感じているのですが実際のところはどうだったでしょうか。
せっかくなので記事を書こうと思いましたが解法自体は解説に書いてあるし、ただ自分語りしてもしょうがないので、この記事では問題の解法には触れずに問題をどのようにして思いついたかを記述しようと思います。
「こうすれば作問できるよ」みたいな記事は DEGwer さんや milkcoffee さんが書いてくれていて、その記事の中にも実際の作問例がのっています。実際にこれらの記事を参考に作問をしていますが、作問方法というのは十人十色でいろんな人のいろんなサンプルがあった方がいいんじゃないかと思っています。
A 問題
#UV_LT_ABC411
— えく (@eku_6) 2025年7月9日
話してくださった皆さんありがとうございました！
やはりオンサイトのイベントには行くべき
はなまるうどん2次会でお話ししてできたお三方もありがとうございました
めちゃくちゃ楽しかったです
はなまるうどんに競プロer 4 人で行ったときに、自分が先に注文を終えクーポンと共に席に戻ると、席を取ってくれてた人がそのクーポンを持ってうどんを注文しに行った話から作問しました。A がうどんの値段、B がクーポンの数、Q がうどんを注文する列に対応しています。うどん要素を問題文に組み込んだところ、問題文が冗長になってしまったのでうどん要素がない問題文になっています。
B 問題
AHC021 をみて、適当な枠の中でソートする問題を考えていましたがあまりうまくいきませんでした。その中で生まれた「2 行 N 列の枠で縦移動をできるだけ多くする」という設定の問題から派生させました。2 のところが一般で解けることがわかって、今の問題の制約に至ります。
C 問題
DEGwer さんの記事で「考えた設定の個数 × 出題方法のレパートリー = 問題数」と紹介されています。
ただ自分は設定がとにかく思いつかないので、設定で掛け算しようと思って、「Mex」 と「木」が出てくる問題を作ろうとしました。
Mex といえば集合に対する関数ですが、2 要素に限定した Mex は以前も ARC ででていて、始めたての自分にとっては手がつかないし面白い問題だと感じていました。
ということで木の頂点に数字を割り当てて、辺の両端の要素の Mex の総和を最大化する求める問題を考えました。もちろん 01 を適切に割り当てれば最大化できるので、012 の数を指定することにしましたが、そのような形では解けませんでした。
結局円環で総和を最大化するような配置の数え上げをする問題として admin に渡したところ、順列の改題案を出されて、さらにクエリ化しました。
D 問題
次回の #日向坂で会いましょう は…
— 日向坂で会いましょう (@hiraganakmax) 2025年5月19日
【正統派を探せ！緊急ぶりっ子オーディション！！】
新生日向坂になった今、正統派ぶりっ子がいないのでは…そこで今回は緊急ぶりっ子オーディションを開催！
果たして天然の正統派ぶりっ子は現れるのか？五期生の初々しいぶりっ子を目に焼きけろ！
テレビで負け抜けの(古今東西をしながら)爆弾回しゲームをしていて、その番組内では爆弾が爆発するタイミングを MC がくじで引いた秒数で決まっていました。それを見て「MC の引運次第では、贔屓しているメンバーを勝ち残せるのでは」というところからきた問題です。勝ち残らせる人を一人にしたらランダムな順列を作って辻褄合わせるのが強すぎたので、勝ち残らせる人を区間にしました。なんで (R - L, R - L + 1, ... , N - 1) という普通の順列から前 R - L 個を削除した列を並び替える設定かというと、爆弾ゲームの時間は長い方が番組的に面白いかと思ったからです。(そうしたらいい感じの問題になったというのもありますが)
おまけ
ARC167 についてはあまり真面目に書いてないですが以下を参照してください。
ARC178 についてはこの下に簡単に書こうと思います。
A : AGC064F を見て作りました
B : 問題名にもあるように 1 + 6 = 7 から問題を作ろうと思って、桁数を指定することにしました。
C : ARC172B の出力例 4 が恣意的に作られているところから、簡単な問題のサンプルを綺麗に作るという設定ができて、そこから作りました。
D : エジプト行きの飛行機で「純烈から適当な区間を取って、それの Mex を削除する」という設定が思いついて、飛行機の中で出題形式までまとめました。
E : Ants の蟻、自分で向き決められなくて可哀想。もし賢かったら？というところから作問しました。
F : 0,1,2,...,N を文字列で並べたときの転倒数という問題を作っていて、2 進数なら良い計算量で解けることにはなったのですが、より難しくしようとして今の形になりました。
yukicoder No.3146 RE: Parentheses Counting 一般項の導出
問題
正しい括弧列 $T$ に対して、$f(T)$ を以下のように定義します。
- $T_{i} =$
(を満たす全ての $i$ に対する以下の値の総和- $T_{i} =$
(に対応する)を $T_{j}$ としたとき、$T[i + 1:j] ( = T_{i+1}T_{i+2}\cdots T_{j - 1})$ に含まれる連続部分列()の数
- $T_{i} =$
$N$ が与えられるので、長さ $N$ の全ての正しい括弧列 $S$ に対する $f(S)$ の総和を $998244353$ で割ったあまりを求めてください。
解説
$N$ は偶数であることを仮定します。
$N = 2n$ とします。
$T$ の連続部分列として、 () が含まれているとき、その () の $f(T)$ に対する寄与は () の高さになります。つまり、 () の前にある ( の数から ) の数を引いた値です。
この「( の数から ) の数を引いた値」が $K$ であるとき、$T$ は以下のように分解できます。
- 「正しい括弧列 +
(」が $(K + 1)$ 個 + 「)+ 正しい括弧列」が $(K + 1)$ 個
これは以下の形で表せる長さ $2n - 1$ の文字列と一対一対応します。
- 「正しい括弧列 +
(」が $(2K + 1)$ 個 + 「正しい括弧列」
このような文字列は、鏡像法を用いると、$\binom{2n - 1}{n + K} - \binom{2n - 1}{n + K + 1}$ になります。
この鏡像法の使い方がわからない人は以下のブログを参照してください。もしくは、カタラン数の母関数の pow だと思っても良いです。$[x^{n - K - 1}]C^{2K + 2}(x)$ と同じ値です。
よって、答えは以下のようになります。
$$\sum_{K = 0}^{n - 1}K\left(\binom{2n - 1}{n + K} - \binom{2n - 1}{n + K + 1}\right) = \sum_{K = 1}^{n - 1}\binom{2n - 1}{n + K}$$
ここからは以下のように式変形すると、解説にもある一般項が導出できます。
$$\sum_{K = 1}^{n - 1}\binom{2n - 1}{n + K} = \frac{1}{2}\left(\sum_{k = 0}^{2n - 1}\binom{2n - 1}{k}\right) - \binom{2n - 1}{n} = 2^{2n - 2} - \binom{2n - 1}{n}$$
冪級数を用いる方針
以上の話をまとめると、$N = 2n$ のときの答えが $[x^{n}]f(x)$ で表されるような冪級数 $f$ は以下のように表されます。
$$f(x) = \sum_{K = 0}^{\infty}K(xC^{2}(x))^{K + 1} = \left(\frac{xC^{2}(x)}{1 - xC^{2}(x)}\right)^{2}$$
ここで、$s = \sqrt{1 - 4x}$ とすると、以下の変形が成り立ちます。
$$xC^{2}(x) = x\left(\dfrac{1 - s}{2x}\right)^{2} = \dfrac{(1 - s)^{2}}{4x}$$
$$1 - xC^{2}(x) = \dfrac{4x - (1 - s)^{2}}{4x} = \dfrac{1 - s^{2} - (1 - s)^{2}}{4x} = \dfrac{s(1 - s)}{2x}$$
よって、答えについて以下が成り立ちます。
$$f(x) = \left(\dfrac{(1 - s)}{2s}\right)^{2} = \dfrac{1 - 2s + s^{2}}{4s^{2}} = \frac{1}{4(1 - 4x)} + \frac{1}{2\sqrt{1 - 4x}} + \frac{1}{4}$$
中心二項係数と呼ばれているものから、以下が成り立ちます。
$$[x^{a}]\frac{1}{\sqrt{1 - 4x}} = \binom{2a}{a}$$
参考
よって任意の正整数 $n$ について、以下が成り立ちます。
$$[x^{n}]f(x) = [x^{n}]\left(\frac{1}{4(1 - 4x)} + \frac{1}{2\sqrt{1 - 4x}} + \frac{1}{4}\right) = 4^{n - 1} + \frac{1}{2}\binom{2n}{n} = 4^{n - 1} + \binom{2n - 1}{n - 1}$$
CodeChef Starters 186 P6 MEX and XOR 2
問題
正整数 $N$ が与えられるので、$\{0, 1, \dots, N\}$ の空でない部分集合 $S$ であって、$\mathrm{MEX}(S) = \mathrm{XOR}(S)$ を満たすものの場合の数を $998244353$ で割ったあまりを求めてください。
制約
$1\leq$ テストケース数 $\leq 100$
$1\leq N \leq 10^{9}$
目標
公式解説 には時間計算量 $O(\log^{3}(N))$ で解けると書いてありますが、実際には $\Theta(\log(N))$ で解くことができます。このブログでは、$\Theta(\log^{2}(N))$ で解く方法を記します。
解説
任意の整数 $x$ について、$\mathrm{MEX}(S) = \mathrm{XOR}(S) = x$ を満たす $S$ が何通りかを計算します。$x = N + 1$ のときは、$N$ を $4$ で割ったあまりが $2$ か否かで決まります。
$0\leq x\leq N$ のときは、以下の条件を満たしていれば $S$ が少なくとも $1$ つ存在します。
- $A = \lfloor\frac{N + 1}{4}\rfloor\cdot 4$ としたとき、$x< A$ が成り立つ。
詳しくは説明しませんが、任意の正整数 $a$ に対して$\mathrm{XOR}(\{0, 1, \dots, 4a - 1\}) = 0$ であることから、 $x< 4a$ であるとき $T = \{0, 1, \dots, 4a - 1\} \setminus \{x\}$ とすると、$\mathrm{XOR}(T) = \mathrm{MEX}(T) = x$ がなりたつことから示せます。
$x< A$ を満たす $x$ に対して、$\mathrm{MEX}(S) = \mathrm{XOR}(S) = x$ を満たす $S$ は何通りあるかというと、以下のようにして求めれられます。
- $\{x + 1, x + 2, \dots , N\}$ の xor に関する空間の基底の個数を $b$ としたとき、$2^{N - x - b}$ 通り
$x = 0$ のときは $S$ が空のときがあるので、注意します。$b$ の値が変わらない区間に対する $2^{N - x - b}$ の総和は、等比数列の総和なので、簡単な式になります。よって、$b$ が変化するタイミングが全てわかれば良いです。結局以下の問題に帰着されました。
サブ問題 1
$0\leq x\leq N$ を満たす整数 $x$ であって、以下の条件を満たすものを列挙してください。
- $\{x + 1, x + 2, \dots , N\}$ の部分集合 $S$ であって、$\mathrm{XOR}(S) = x$ を満たすものが存在しない。
この問題はさらに以下の問題と同値です。
サブ問題 2
$f(x)$ を以下のように定義します。
- 「$\{x + 1, x + 2, \dots , A\}$ の部分集合 $S$ であって、$\mathrm{XOR}(S) = x$ を満たすものが存在しない。」を満たす、最大の整数 $A$
$0\leq x\leq N$ を満たす整数 $x$ であって、$N \leq f(x)$ を満たすものを列挙してください。
サブ問題 2 解説
この $f(x)$ に関して、以下が成り立ちます。
- 正整数 $a$ を用いて、$x = 2^{a} - 1$ と表せるとき、$f(x) = 3\cdot 2^{a - 1} - 1$
- 正整数 $a, b$ を用いて、$x = 2^{a}b+(2^{a - 1} - 1)$ と表せるとき、$f(x) = x + 2^{a}$
$x = 2^{a} - 1$ のとき
以下のように $y, z$ を定めます。
x = 111...11 y = 1011...11 z = 1100...00
すると、$x = \mathrm{XOR}(\{y, z\})$ がなりたつので、 $f(x) < z$ です。また、$x$ より大きくて、$2^{a - 1}$ の位が $1$ になる最小の整数が $z$ であることから、$z - 1\leq f(x)$ です。よって、$f(x) = z - 1$ です。
$x = 2^{a}b+(2^{a - 1} - 1)$ のとき
$x$ を $2$ 進数表記すると、下に $1$ が $(a - 1)$ 個続いたあと、$0$ がくるような形になります。
以下のように $w, y, z$ を定めます。
x = b + 011...11 w = b + 100...00 y = succ(b) + 011...11 z = succ(b) + 100...00
すると、$x = \mathrm{XOR}(\{w, y, z\})$ がなりたつので、 $f(x) < z$ です。$x < c < z$ を満たす整数 $c$ は以下のように表せる $c1, c2$ に限ります。
c1 = b + 1??...?? c2 = succ(b) + 0??...??
$2^{a - 1}$ の位のことを考えると、$c1$ のように表せるものは偶数個しか採用できません。よって、$x < c < z$ を満たす整数 $c$ の集合の部分集合をとったものの $\mathrm{XOR}$ は $2^{a}$ で割った商が $0$ もしくは $\mathrm{succ}(b)$ に限ることから $z - 1\leq f(x)$ です。よって、$f(x) = z - 1$ です。
まとめ
以上を用いると、$a$ ごとに $N < f(x)$ がなりたつ $f(x)$ を列挙すれば良いです。そのような $x$ の数は $\Theta(\log(N))$ 通りしかないので、以下のように実装すれば全体の計算量は $\Theta(log^{2}(N))$ となります。
#include <bits/stdc++.h> using namespace std; #define rep(i,a,b) for (int i=(int)(a);i<(int)(b);i++) #include <atcoder/modint> using mint = atcoder::modint998244353; void solve(){ int N; cin >> N; // 基底を列挙する vector<int> base; // 基底を全て求める。 // 2^a - 1 タイプ { int a = 0; while ((1 << (a + 1)) - 1 <= N) a++; if (N < (3ll << (a - 1))) base.push_back((1 << a) - 1); } // 普通のタイプ { for (int a = 0; (3ll << a) - 1 <= N; a++){ int tmp = (N - ((1 << a) - 1)); tmp >>= (a + 1); tmp <<= (a + 1); tmp += (1 << a) - 1; while (tmp != (1 << a) - 1 && N <= tmp + (1 << (a + 1))){ base.push_back(tmp), tmp -= (1 << (a + 1)); } } } sort(base.begin(), base.end()); reverse(base.begin(), base.end()); base.emplace_back(0); base.insert(base.begin(), N + 1); mint ans = 0; int A = ((N + 1) / 4) * 4; for (int i = 1; i < (int)base.size(); i++){ int L = base[i], R = min(A, base[i - 1]); if (L < R){ ans += (mint(2)).pow(N + 2 - L - i) - (mint(2)).pow(N + 2 - R - i); } } if (N % 4 == 2) ans += 1; if (N >= 3) ans -= 1; cout << ans.val() << "\n"; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t = 1; cin >> t; rep(i, 0, t) solve(); }
計算量改善
基底に含まれる任意の値 $b$ に対して、$\frac{1}{2^{b}}$ が事前にわかっていれば、全体の計算量が $\Theta(\log(N))$ になります。$b$ の bit のずれが少ないことから、$\frac{1}{2^{b}}$ の列挙は時間計算量 $\Theta(\log(N))$ で求められます。よって、全体の計算量も $\Theta(\log(N))$ です。
おまけ
この基底の列は、rns_kwg さんの提出を見ると、以下のように求めることができます。
int up = 32 - __builtin_clz(N); vector<int> base = {N}; for (int i = 0, j; i < up; i = j + 1){ for (j = i; j < up; j++) if ((N >> j) & 1) break; int a = ((N >> j) << j) - 1; base.emplace_back(a); for (int k = i; k < j; k++) base.emplace_back(a ^ (1 << k)); } base.pop_back();
なぜこれでいいのかの理由はわかっていないです。
