cLay ドキュメント（version 20241019-1）

目次（全然未完成，整理中です…すみません）

概要など

型と変数宣言

入出力

ループ
演算子
グラフ
データ構造

整数

幾何
行列
配列

文字列
典型手法

典型問題
その他（未整理）
更新履歴

概要など

概要

C++っぽい言語をC++言語に変換します．
無駄にライブラリを張るのがめんどくさい，鬱陶しい，ライブラリを整備していても綺麗に書けない処理があるなどを解消したいというのが目的．目的の達成はそのうち…．
blogにコード載せる時にライブラリとかincludeとかが長ったらしい，のをなんとかしたいというのも動機の1つです．

C++っぽいコードを標準入力から食わせるとC++のコードが標準出力から出てきます．

#include<bits/stdc++.h>およびgetchar_unlocked，putchar_unlockedなどを使用しているので，それが動かない環境だと動かないし，動かないコードが出てきます．
（その場合は，フラグの欄を見て下さい）

cLayの概要のページはこちら．
最新のバージョンへのリンク：コードとドキュメントを含むzipファイル／プログラムのコード／ドキュメント．
過去のバージョンを含むコードの公開ページはこちら（不定期更新）．

ローカルでこのドキュメントを見る場合は，このhtmlファイルと同じフォルダにfontフォルダを作成し，その中にM+ FONTS（mplus-1p-light.ttfなどのmplus-*.ttfファイル）を入れるとオンライン版と同じように表示されると思います．
実際に使用しているのは mplus-1p-light, mplus-1p-heavy, mplus-1p-bold, mplus-1p-regular, mplus-1m-light の5種類だと思います．

未対応なもの

重要度が高い順に，下線付き太字，太字，普通です．重要度が低いものはそもそも対応させる気がないものが多いです．
この欄ではC++ではできるけど…というもの主にリストアップ．

制限

以下の単語は変数名などで使うとやばい．
基本的にバージョンアップするときは互換性を保ちたいけど，此処の欄は普通に増やす．

色々書いてたけどめんどくさくなったので省略．

int は32bit，long は32bitか64bit，long long は64bitだと思って実装しています．違うとまずい場合があるかも．

色々

最初に

#include<bits/stdc++.h>
using namespace std;

が強制的に挿入されます．
#includeを書く必要はないですが，GCC以外で動かなくなる．

int main()は省略可能です．
いきなり関数の中じゃなくて{で始まるブロックが最初に出てきたときにint main()が補われます．
int main()で補われたブロック内の最後がreturn文でない場合は，return 0; が最後に補われます．
main関数がなく，if文やfor文などがつかないブロックもない場合，プログラムの最初に int main(){ が，最後に } が補われます．

変数宣言や三項演算子 ? : を使っていない部分での,は（適切に{}を補った上で）;に置き換えられます．
その結果，for(;;) i++, break; などと書くと for(;;){ i++; break; } に展開されます．

cpp_int が出てくると，boostの多倍長整数を利用できるように

#include <boost/multiprecision/cpp_int.hpp>
using namespace boost::multiprecision;

が挿入されます．

フラグ

途中で（プログラムの先頭が推奨）
//hogehoge
という形式でフラグを立てておくと色々な環境に対応させるために出力されるコードが変更されます．

またmint構造体など使用すると挿入される関数や構造体を挿入されなくするフラグは以下の通りです．
例えば，//no-insert-mintを指定するとmint型が使えなくなる代わりに，mintという変数や関数などを自由に宣言することができるようになります．

型と変数宣言

型の省略形

ll は long long に，ull は unsigned long long に置き換えられます．
VI は vector<int> に，VVI/VII は vector<vector<int>> に，VVVI/VIII は vector<vector<vector<int>>> に置き換えられます．
VLL は vector<long long> に，VVLL は vector<vector<long long>> に，VVVLL は vector<vector<vector<long long>>> に置き換えられます．
VS は vector<string> に置き換えられます．

modint型など

mint型が使えます．
mod MDで計算します（MDは#define MD hogeで定義しなければデフォルトでは10^9+7が使用されます．MDは奇素数でなければ上手く動かない可能性があります．定数の項も参照のこと）．
四則演算（割り算も）は使えます．int型やll型などと計算すると結果はmint型になります．
mint型の法の設定などはmain関数の変数宣言後に行うので，変数宣言時に代入などすると上手く動かないので，変数宣言時に代入するのは避けたほうが良いです．
mint x; x = 1; x /= 2; wt(x); で 500000004 が表示されます．
また，べき乗 pw が使えます．
mint x, p; x = 2; p = x.pw(100); で p に $2^{100} \bmod (10^9+7)$ が代入されます．
mint x; x.setmod(1000000009); とすることで，途中で mod の値を変えることができます．
mintの詳しい仕様はそのうち書きます．

モンゴメリ乗算を使用しないmodint型もあります．
MDが素数でなくても，割り算をしなければmodint型は動くと思います．
mint型とmodint型はほぼ同じ使用方法です．

途中で mod を変更できないバージョンとして1文字目を大文字にした Mint, Modint があります．
こっちのほうが高速なはず．初期化も必要ないので，変数宣言時に代入しても大丈夫なはず．
mint, modint, Mint, Modint はコンストラクタで 0 に設定されるはずです．

配列の変数宣言

配列のサイズを省略し，初期化もしていない場合，直前に確保した同じ次元の配列の対応する次元サイズになります．

int A[1d5], B[], m[100][100], C[];
int x[][], y[] = {1,2};
int s[10][], t[][];

は以下のようになります．

int A[100000];
int B[100000];
int m[100][100];
int C[100000];
int x[100][100];
int y[] = {1,2};
int s[10][100];
int t[10][100];

配列の初期化は，現状 = を明示的に書いている場合のみ初期化しているとみなします．
以下の例で，int y[]{1,2} と書いた場合は，int y[1d5]{1,2} と 1d5 が配列サイズとして設定されます．
将来的に変更される可能性があります．一般的な用途としては，一応この場合は配列サイズを省略しないのを推奨とさせてください．

入出力

入力

unlocked シリーズが使えない場合は，//no-unlocked フラグを指定してください．unlocked じゃないものを利用します．

rd(i, j, k) で標準入力からi,j,kが読み込まれます．scanf("%d%d%d",&i,&j,&k); などと似た感じですが，スペース区切りじゃなく，数字以外で区切られます．
rd(i, j(n), k)はrd(i, j[0], j[1], ..., j[n-1], k)に置き換わります（左から処理するのでrd(n, A(n))とか可能です）．
また，rd(N, (A,B)(N)) は rd(N, A[0], B[0], A[1], B[1], ..., A[N-1], B[N-1]) に置き換わります．グラフのエッジの入力とかに．
2次元の入力は rd(arr(3,3)) で rd(arr[0][0], arr[0][1], arr[0][2], arr[1][0], arr[1][1], arr[1][2], arr[2][0], arr[2][1], arr[2][2]) になります．3次元以上も同様．
rdの代わりにreaderでもOK．
rdは今のところint型，unsigned型，ll型，ull型，double型（指数表記は対応していない），mint型，char型（1文字），char型の配列（文字列），string型，vector<T>，Matrix<T>，Permutation，IntMap，Grid1d<T>，Grid2d<T>にのみに対応．ただし，Tは対応している型でなければならない．他の型もそのうち対応．
また，char S[1000]; int N; rd(S@N);で文字列 S を読み込むと同時に文字列の長さを N に代入します．複数の文字列の場合は char S[10][1000]; int N[10]; rd(S@N(10)); とS@Nはひとかたまりで扱います．
char型1文字の入力の場合も，空白などは読み飛ばして，次の空白でない文字を読み込みます．

rd(i--) は rd(i); i--; になります．++もできます．2減らすなら rd(i----) です．
rd((A--)(N)) は配列AのN個の要素すべてが1減ります．カッコは必須です．rd(A--(N)) は書けません．
rd((A--,B--,C)(N)) は配列A，Bの要素は1減り，Cの要素はそのままです．
1-originから0-originに直しながら入力するときなど．

A[2], B[4], A[3], B[5], A[4], B[6] に読み込みたい場合は rd(((A+2),(B+4))(3)); で可能です．
A[2], A[3], A[4] に読み込む場合は rd(((A+2))(3)); で可能です（かっこが多すぎる気がしますが，現状これだけ必要です…：(A+2)[0], (A+2)[1], (A+2)[2]でアクセスします）．

int len; char buf[100];
len = rdLine(buf); で1行の読み込みを行います．
正確には，\n か EOF に出くわすまでbufに入れていきます（\nは入らない）が，\rだけは無視されます．
lenには基本的に読み込んだ文字数を返しますが，1文字も読み込まずEOFに出くわした場合のみ-1を返します．
bufの最後の文字の次に \0 を入れて返します．

変数に代入しないものとして，以下の関数は次の入力をその型の値として戻り値で返します．

出力

wt(i, j, k)でスペース区切りでi, j, kを標準出力に吐き出し，改行します．
wt(i, j(n), k)はwt(i, j[0], j[1], ..., j[n-1], k)に置き換わります．
また，wt(N, (A,B)(N)) は wt(N, A[0], B[0], A[1], B[1], ..., A[N-1], B[N-1]) に置き換わります．式の一部がこの形でも同様に置き換わります（以下の例を参照）．
最後に改行する代わりにスペースを出力する場合はwtの代わりにwtSpを，改行区切りで出力する場合はwtLnを使います．また区切りに何も出力しない場合はwtNを使います．
wtの代わりにwriter，wtSpの代わりにwriterSp，wtLnの代わりにwriterLnでもOK．
wtは今のところint型，ll型，double型，mint型，char型の配列（文字列），string型と，vector, set, multiset, pairの組合せのみに対応．他の型もそのうち対応．
wtF は引数に "" で囲まれた文字列をそのままの形でわたし（式を書けない），その文字列を出力しますが，変数名を{}で囲むと，その変数の値に置換されて出力されます．文字列中で{または}を出力したい場合はエスケープして\{または\}と書きます．

関数 wt(f(a)) は，fが変数として認識されてないと f(0), f(1), ..., f(a-1) に展開されませんが，fが変数として認識されていると展開してしまいます（特に構造体を作ってその変数fを定義している場合）．
配列の展開しない場合，Wt(f(a)) や Writer(f(a)) のように W を大文字にしてください．

double型の変数を wt() で出力する場合，デフォルトでは小数点以下15桁表示します．
10桁表示したい場合は，事前に writerDigit_double(10); としてください．
また，現在の表示桁数を取得する場合は，writerDigit_double(); で取得できます．
中身が NaN, Inf などの変数を表示させた場合，現状は Err と表示されます．

2次元以上の配列の出力は，wtLn など区切り文字を明示的に指定したものを使うと各要素がそれで区切られます．
wt を使った場合，配列単体を出力する場合，および，出力の最後が配列の場合は，配列の最後のインデックスに対して1行に出力されます．
wt(arr(2,3)) の場合は，

arr[0][0] arr[0][1] arr[0][2]
arr[1][0] arr[1][1] arr[1][2]

となり
wt(arr(2,2,3)) の場合は

arr[0][0][0] arr[0][0][1] arr[0][0][2]
arr[0][1][0] arr[0][1][1] arr[0][1][2]
arr[1][0][0] arr[1][0][1] arr[1][0][2]
arr[1][1][0] arr[1][1][1] arr[1][1][2]

と出力されます．最後の要素でない場合は，1行に出力されます．
wt(arr(2,3), "hoge", 100) の場合は

arr[0][0] arr[0][1] arr[0][2] arr[1][0] arr[1][1] arr[1][2] hoge 100

です．

また，出力に関してオプションで B=n と指定すると整数系のものは n 進数で出力されます．
例えば，wt[B=3]("hello", 10); は hello 101 と出力されます（文字列に関しては基数は無視されます）．
62進数まで指定可能で，文字は 01...9ABC...Zabc...z の順番です．

例:

int N, A[10], B[10], res[10];
rd(N, (A,B)(N));
wt(N, 2*res(N)+1);

は以下と同じ意味になります．

int i, N, A[10], B[10], res[10];
scanf("%d", &N);
for(i=0;i<N;i++) scanf("%d%d", A+i, B+i);
printf("%d ", N);
for(i=0;i<N;i++) printf("%d%c", 2*res[i]+1, i==N-1?'\n':' ');

また

int T = 0, res = 10;
wtF("\{Case {++T}: {res}\}\n");

は以下と同じ意味になります．

int T = 0, res = 10;
printf("{Case %d: %d}\n", ++T, res);

また

int N, L[10];
char S[10][1000];
rd(N, S@L(N));

は以下と同じ意味になります．

int i, N, L[10];
char S[10][1000];
scanf("%d",&N);
for(i=0;i<N;i++){
  scanf("%s",S[i]);
  L[i] = strlen(S[i]);
}

vector, set, multiset, pair については，中身の要素をスペース区切りで1行にまとめたものがひとかたまりとみなされます．
中身が整数であっても [B=2] などで進数を指定しないでください．現状は指定しても10進数で表示し，将来的に仕様は変わる可能性があります．
例えば，

int a = 1;
VI b{2,3,4};
int c = 5;
wt(a,b,c);
wt("---");
wtLn(a,b,c);
wt("---");
wtLn(a,b(b.size()),c);

に対する出力は

1 2 3 4 5
---
1
2 3 4
5
---
1
2
3
4
5

となり，

set<VS> s;
s.insert(VS{"hoge", "piyo", "hoge"});
s.insert(VS{"a", "z"});
s.insert(VS{"hoge", "piyo", "hoge"});
wtLn(s);

に対する出力は

a z hoge piyo hoge

となり，

multiset<VS> s;
s.insert(VS{"hoge", "piyo", "hoge"});
s.insert(VS{"a", "z"});
s.insert(VS{"hoge", "piyo", "hoge"});
wtLn(s);

に対する出力は

a z hoge piyo hoge hoge piyo hoge

となり，

pair<int,pair<double,string>> p = make_pair(10, make_pair(20.0, "abc"));
wt(p);

に対する出力は

10 20.000000000000000 abc

となります．

細かい注意

reader(), writer() は複数の文に分割されることがあります．
1文に reader(), writer() が単独でなくなる場合に現状うまく動きません．
（とりあえずは ; で区切って単独の文にしてもらえると助かります）

wt(1?1:0),wt(1);          // うまく動かない
if(cond) a=a?a:b, wt(a);  // うまく動かない
wt(1),wt(2);              // 三項演算子がないので wt(1); wt(2); となりwt単独になるので問題なく動く

ファイル入出力

標準入出力ではない場合は，readerFile()，writerFile()を利用して入出力先を指定します．
ファイル名（勝手にfopen, fcloseされる）かファイルポインタを引数に指定します．

  int i, j, k;

  rd(i); // stdinから読み込み
  readerFile("input.txt");
  rd(j); // input.txtから読み込み
  readerFile();
  rd(k); // stdinから読み込み

  wt(i); // stdoutに書き込み
  writerFile("output.txt");
  wt(j); // output.txtに書き込み
  writerFile("log.txt", "a");
  wt(k); // log.txtに追加で書き込み "a"モードで開く
  writerFile(stderr);
  wt("hoge"); // stderrに書き込み

という感じです．

変数宣言時の入力

変数を宣言した際に変数名の前に@をつけると，その時点でrd()を利用して入力します．
@と変数名の間，または変数名の後に++や--を書くと，読み込んだ瞬間インクリメント，デクリメントをします．
（int @++A; でも int @A++; でも int @++A[10]; でも int @A++[10]; でも int @A[10]++; でも良いですが，int ++@A; や int @A[++10]; はやめて下さい．通常の意味の int @A[N++]; も避けて下さい）
配列の場合は，配列サイズだけ読み込みます（2次元以上の配列でも大丈夫です）．

{
  int @A, @B, res = abs(A-B)/+10;
  wt(res);
}

は

{
  int A;
  rd(A);
  int B;
  rd(B);
  int res = abs(A-B)/+10;
  wt(res);
}

となります．

{
  int @N, @A++[N];
  wt(mul(A(N)));
}

は

{
  int N;
  scanf("%d",&N);
  int A[N];
  int i;
  for(i=0;i<N;i++) scanf("%d",&A[i]);
  for(i=0;i<N;i++) A[i]++;
  int res = 1;
  for(i=0;i<N;i++) res *= A[i];
  printf("%d\n", res);
}

の意味です．

int @(A,B)[N]; で A[0], B[0], A[1], B[1], ... の順番で読み込みます．
（この書き方は @ が必須です．int (A,B)[N]; で入力を読み込まずに変数宣言だけ行うことはできません）
また，変数名の前に，型を書くと，その変数だけその型になります．

int @N, @(A,B++)[N];

は

int N;
scanf("%d",&N);
int A[N], B[N];
for(int i = 0; i < N; i++){
  scanf("%d%d\n",A+i,B+i);
  B[i]++;
}

の意味となり，

int @N, @(A,B,ll C,D)[N];

は

int N;
scanf("%d",&N);
int A[N], B[N]; ll C[N]; int D[N];
for(int i = 0; i < N; i++) scanf("%d%d%lld%d\n",A+i,B+i,C+i,D+i);

の意味になります．

また，vector に関しては，@変数名(要素数) という形で宣言した場合に，標準入力より読み込みます．
例えば，

int @N;
VLL @(A,B)(N);
VI @C(N);

は

int N;
scanf("%d",&N);
vector<long long> A(N), B(N);
for(int i = 0; i < N; i++) scanf("%lld%lld\n",&A[i],&B[i]);
vector<int> C(N);
for(int i = 0; i < N; i++) scanf("%d\n",&C[i]);

の意味になります．

チェック付き入力

読み込んだ値がmn以上mx以下でない場合は assert() により落ちてREになります．
また，値の前に余分なスペースや文字などがある場合も assert() により落ちてREになります．
読み込んだ直後の文字が nx でない場合も assert() により落ちてREになります（nxまで読み込んだことになり，次はnxの次の文字から読み込みます）．
先頭に余分な0がある場合（0038, -01，00 など），「-0」と0の前にマイナス記号が存在する場合も落ちます．

入力形式が

N
A B C

で制約が $1 \leq N \leq 100$，$0 \leq A \leq B \leq C \leq 10^9$ の場合は

ll N, A, B, C;
N = cReader_ll(1, 100, '\n');
A = cReader_ll(0, 1d9, ' ');
B = cReader_ll(A, 1d9, ' ');
C = cReader_ll(B, 1d9, '\n');
cReader_eof();

などで入力形式等が正しいかチェックしながら読み込むことができます．

ループ

演算子

グラフ

データ構造

UnionFind (UF, Disjoint Set Union, USU)

unionFind構造体．unionFind uf; で宣言したとして以下の通り．

以下あまり使わないやつ

weightedUnionFind 構造体．いわゆる重み付きUnionFind．
weightedUnionFind<T> uf; で宣言したとして以下の通り．
unionFindとの差分のみを記述．connectの使い方が違うのと，diffが追加されています．

weightedUnionFind<ll> uf('w',100,1);
uf(10,70,1000LL);
uf(70,90,2000LL);
if(uf(10)==uf(90)){
  wt("connected");
  wt(uf.diff(10,90)); // 3000
}

rollbackUnionFind 構造体．rollbackUnionFind uf; で宣言したとして以下の通り．
ただし，unionFindで使えるものは全てそのまま使える．
経路圧縮をしないので，一部の計算量はアッカーマン逆関数からlogになっている．

整数

桁・n進数

配列の最初の要素が一番小さい桁に対応します（i番目の要素が10^iに対応，など）．
最後に_rがついている関数に関しては，逆に配列の最初の要素が一番大きい桁に対応します（数値を文字列として読み込んだ場合に対応，など）．

ルートとk乗根

どれもllの最大値に近いとうまく動かない可能性がある（4*10^18ぐらいまでを目安に）．
整数の平方根．（ただし n として ll でオーバーフロー直前みたいなのを引数に与えると動かない可能性が高い）

整数の立方根．
現在は非負整数のみに対応だが，将来的に負の整数に対応する可能性がある．その場合，Icbrt_s(-8) などは答えが変わる可能性があるので注意．

整数のk乗根．
現在は非負整数のみに対応だが，将来的に負の整数に対応する可能性がある．

log2

整数のlog2．
内部で __builtin_clz や __builtin_ffs 系列の関数を使用しています．GCC系以外では動かないかもしれません．
入力が 0 以下なら -1 を返します．
Ilog2の最初の文字は大文字のアイ，2文字目は小文字のエルです．

ビット

ビットに関すること．

幾何

行列

配列

ソート（配列）

配列に関するソート．
状況に応じてバケツソート・基数ソート・イントロソートなどを使い分けます．
変な不都合が出る場合などは，単純にイントロソート（srd::sortを使う）をする sortI() を使ってください．
現状は，配列の数が3以上になると，イントロソートのみを試します．

以下は古いもの・あまり使わないもの．

ここまで（以下は古いもの・あまり使わないもの）

  int i;                               // (1,2)      ←出力結果
  int A[5] = {3,1,3,5,2};              // (2,5)
  int B[5] = {1,2,3,4,5};              // (3,1)
  sortA(5,A,B);                        // (3,3)
  rep(i,5) wtF("({A[i]},{B[i]})\n");   // (5,4)

ソート（変数）

主に1つの配列に関する処理

スライス
添字が bg から ed まで step 飛ばしで 配列 A の要素を拾ってできる配列を返す求める．
A[bg], A[bg + step], A[bg + 2*step], A[bg + 3*step], ..., A[bg + (len-1)*step] みたいなのを返す．
step が正なら，bg 以上 ed 未満の添字からなる
step が負なら，bg 以下 ed より大きい添字からなる
N を配列Aの長さとして，添字が 0 以上 N 未満でなければ，A は循環していると思って A[ind] = A[ind mod N] みたいに思う

int N = 10, A[10] = {0,1,2,3,4,5,6,7,8,9};
int len, B[20];

len = Slice(N,A,0,2N,1,B);
wt(len, ":", B(len));

len = Slice(N,A,10000000000005LL,10000000000010LL,2,B);
wt(len, ":", B(len));

len = Slice(N,A,5,0,-1,B); // including A[5], excluding A[0]
wt(len, ":", B(len));

len = Slice(N,A,3,-40,-13,B); // (A[3], A[-10], A[-23], A[-36]) = (A[3], A[0], A[7], A[3])
wt(len, ":", B(len));

len = Slice(N,A,3,10,-1,B);
wt(len, ":", B(len));<MYFORMAT_TEX_BR>

/*
20 : 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
3 : 5 7 9
5 : 5 4 3 2 1
4 : 3 0 7 4
0 : 
*/

配列のシフト

主に1つの配列に関する計算

相異なる要素数をカウントする

とある要素の数をカウントする

とある要素が連続する最大長さを求める

回文にするのに変えないといけない要素数
A[i] != A[N-1-i] の数を数える（i=0,1,...,N/2-1）

string str1 = "aabbcc", str2 = "abcbd";
wt(PalindromeCost(str1), PalindromeCost(str2));
// 2 1

string str = "aabbaa";
rep(i,1,str.size()+1) wt(i, ":", PalindromeCost(str.substr(0,i)));
// 1 : 0 (a)
// 2 : 0 (aa)
// 3 : 1 (aab)
// 4 : 2 (aabb)
// 5 : 1 (aabba)
// 6 : 0 (aabbaa)

Mex

K番目の要素

主に2つの配列に関する処理

ソートしながらマージする（マージソートのマージ）

マージテク（要素数が小さい方だけ移動させることで計算量を削減するテクニック）のマージ
AにBの要素を追加して，Bを空にする（並び順はどうなるか不明）

set<int> a1( {3,4,5,6} );
set<int> b1( {1,2,4,8,16} );

MergeTech(a1,b1);
wt(a1); // 1 2 3 4 5 6 8 16
wt(b1); // none

multiset<int> a2( {3,4,5,6} );
multiset<int> b2( {1,2,4,8,16} );

MergeTech(a2,b2);
wt(a2); // 1 2 3 4 4 5 6 8 16
wt(b2); // none

vector<int> a3( {3,4,5,6} );
vector<int> b3( {1,2,4,8,16} );

MergeTech(a3,b3);
wt(a3); // 1 2 4 8 16 3 4 5 6
wt(b3); // none

主に2つの配列に関する計算

比較

ワイルドカード文字がある場合の一致判定

string a = "at**der";
string b = "a**oder";
string c = "c******";
string d = "******";


wt( WildEQ(a,b,'*') ); // 1
wt( WildEQ(a,c,'*') ); // 0
wt( WildEQ(a,d,'*') ); // 0

配列Aの 最初, 最後 の部分が配列Bに一致するかを調べる（関数名に三単現のsはないです）

string a = "abc";
string b = "ab";
string c = "bc";

wt( startWith(a,b) ); // 1
wt( startWith(a,c) ); // 0
wt( startWith(b,a) ); // 0

wt( endWith(a,b) ); // 0
wt( endWith(a,c) ); // 1
wt( endWith(c,a) ); // 0

主に複数の配列に関する処理

主に複数の配列に関する計算

典型手法

尺取法（TwoPointers）

長さ n 配列の配列 a に対して，条件が成り立つ区間（空でない連続部分列）を尺取法で求めるものです．
ただし，条件は「空の区間に対して成り立つ」と「条件が成り立つ区間に包含される区間でも成り立つ（短いほど成り立ちやすい）」が成り立たなければいけません．
（実際には，a は配列である必要はありませんが，配列として説明しています）

初め空の区間から初めて，要素を追加したり，削除しながら条件が成り立つか調べます．
TwoPointers(n, res, ind)[追加][削除][条件]; という形式で記述します．
追加では，a[ind]（ind番目の要素）が追加されるときの処理，
削除では，a[ind]（ind番目の要素）が削除されるときの処理，
条件では，条件を満たしているかどうか調べる関数の中身（return で bool を返す）を記述してください．
この記述の前に必要な前処理（初期化）をしておいてください．

resは計算結果を格納する整数の配列（長さn以上）で，j=res[i] というのは，区間 [i,i), [i,i+1), [i,j) は条件を満たすが [i,j] は条件を満たさない（または j=n）を意味します．
条件を満たす区間の最大長は max(res[i] - i) で，区間の数は sum(res[i] - i) です．

例えば，非負整数からなる配列 a に対して，和が10以下になる区間を列挙するには以下のように記述します．

int a[10] = {3,5,1,4,2,11,4,6,1,2};
int res[10], s = 0; // 和 s は 0 で初期化しておく

TwoPointers(10, res, ind)[
  s += a[ind];
][
  s -= a[ind];
][
  return s <= 10;
];

rep(i,10) wt(i,res[i]);
wt("max_len", max[i,0,10](res[i]-i));
wt("num", sum[i,0,10](res[i]-i));

// 0 3
// 1 4
// 2 5
// 3 5
// 4 5
// 5 5
// 6 8
// 7 10
// 8 10
// 9 10
// max_len 3
// num 20

そして，これはだいたい以下のような感じで展開されます（機能追加時の実装っぽいものです）．

{
  int a[10] = {3,5,1,4,2,11,4,6,1,2};
  int res[10], s = 0;

  auto TP_insert = [&](int ind){
    s += a[ind];
  };
  auto TP_erase = [&](int ind){
    s -= a[ind];
  };
  auto TP_check = [&](void){
    return s <= 10;
  };

  {
    int i = 0, j = 0, n = 10;
    for(;;){
      if(TP_check()){
        res[i] = j;
        if(j == n) break;
        TP_insert(j++);
      } else {
        TP_erase(i++);
        res[i] = res[i-1];
      }
    }
    while(i+1 < n) res[++i] = j;
  }

  rep(i,10) wt(i,res[i]);
  wt("max_len", max[i,0,10](res[i]-i));
  wt("num", sum[i,0,10](res[i]-i));
}

典型問題

その他（未整理）

ループ

rep(n) は int hoge; for(hoge=0;hoge<n;hoge++) に置き換えられます（hogeは適当な変数名）．
rep(i,n) は for(i=0;i<(n);i++) に置き換えられます．
rep(i,a,b) は for(i=(a);i<(b);i++) に置き換えられます．
rep(i,a,b,s) は for(i=(a);i<(b);i+=(s)) に置き換えられます．
REP(n) は int hoge, piyo = n; for(hoge=0;hoge<piyo;hoge++) に置き換えられます（hoge, piyoは適当な変数名）．
REP(i,n) は int piyo = n; for(i=0;i<piyo;i++) に置き換えられます（piyoは適当な変数名）．
REP(i,a,b) は int piyo = b; for(i=(a);i<piyo;i++) に置き換えられます（piyoは適当な変数名）．
REP(i,a,b,s) は int piyo = b, huga = s; for(i=(a);i<piyo;i+=huga) に置き換えられます（piyoは適当な変数名）．
また，この際，変数iが宣言されていなかった場合，勝手にint型の変数として宣言されます．
rep では終了条件の変数・式 (n, b) が複数回評価されたり，ループの中で書き換え可能ですが，REP はそうではないことに注意してください．

同じ範囲をループで逆順で回す場合は以下があります（sを指定した場合，必ずしも同じ範囲ではないかもしれない）．
rrep(n) は int hoge; for(hoge=(n)-1;hoge>=0;hoge--) に置き換えられます（hogeは適当な変数名）：使う意味はないです．
rrep(i,n) は for(i=(n)-1;i>=0;i--) に置き換えられます．
rrep(i,a,b) は for(i=(b)-1;i>=(0);i--) に置き換えられます．
rrep(i,a,b,s) は for(i=(b)-1;i>=(a);i-=(s)) に置き換えられます．
RREP(n) は int hoge, piyo = n; for(hoge=piyo-1;hoge>=0;hoge--) に置き換えられます（hoge, piyoは適当な変数名）：使う意味はないです．
RREP(i,n) は int piyo = n; for(i=piyo-1;i>=0;i--) に置き換えられます（piyoは適当な変数名）．
RREP(i,a,b) は int piyo = a; for(i=(b)-1;i>=piyo;i--) に置き換えられます（piyoは適当な変数名）．
RREP(i,a,b,s) は int piyo = a, huga = s; for(i=(b)-1;i>=piyo;i-=huga) に置き換えられます（piyoは適当な変数名）．

配列の中身を変数に代入して使用したい場合は，例えば rep[arr](i,n) hoge; および rep[arr](i,n){ hoge; } は

rep(tekitouna_namae, n){
  auto &i = arr[tekitouna_namae];
  hoge;
}

に展開されます．rep, REP, rrep, RREP それぞれ，引数の数も自由です．
また，インデックスも利用する場合，例えば rep[arr,ind](i,n) hoge; および rep[arr,ind](i,n){ hoge; } は

rep(ind, n){
  auto &i = arr[ind];
  hoge;
}

に展開されます．
変数 i は既に宣言されていても，ブロックの中で再び定義されます．

ループから抜ける break について，二重ループから抜ける break_break などがあります．
break_break は break した後，その直後に break したのと同じ挙動になるはずです．
3重ループを抜ける break_break_break や，一つ上のループに対して直接continueをする break_continue などがあります．
break_ を何回か繰り返して break または continue を最後に付けた文があり，break_A は break を行って，ループを抜けた直後に A を行う感じです．

また，括弧内（(),[],{}のどれか）で2つ以上のドットで区切ると範囲を指定でき，勝手にループに展開されます．
ドットの数が等しいものが同じ変数だと思われて，同じドットの数のものは2回目以降に登場したときには区間の終わりは省略可能です．
（ドットの数が少ない方が内側のループになります．2次元配列のアクセス順で速度がかなり変わるので気をつけたほうが良い場合があります）
例えば，単位行列を作るコード，行列のコピーのコード，転置しながらコピーするコードは

int A[10][10], B[10][10], C[10][10];
A[0...9][0..9] = 0;
A[0..9][0..9] = 1;
B[0...9][0..9] = A[0...9][0..9];
C[0...9][0..9] = A[0..9][0...9];

のように書け，これは

int i, j, A[10][10], B[10][10];
for(i=0;i<=9;i++) for(j=0;j<=9;j++) A[i][j] = 0;
for(i=0;i<=9;i++) A[i][i] = 1;
for(i=0;i<=9;i++) for(j=0;j<=9;j++) B[i][j] = A[i][j];
for(i=0;i<=9;i++) for(j=0;j<=9;j++) C[i][j] = A[j][i];

と同値です（B[0...9][0..9] = A[0...9][0..9];はB[0...9][0..9] = A[0...][0..];と書くこともできます）．

括弧で囲まれていなければならないことに注意して下さい．

A[0..9] = (0..9)
B[0..9] = 50 - (23..)

は

for(i=0;i<=9;i++) A[i] = i;
for(i=0;i<=9;i++) B[i] = 50 - (23 + i);

と同値ですが， A[0..9] = 0..9; などとは書けません．

文字列の中に2個以上ドットが並ぶとバグる実装なのでそのうちなんとかする．

特殊なループ1（多重ループ）

たとえば，

int d[10], n = 10;
rep_perm(d,n){
  hoge;
}

は

int d[10], n = 10;
for(int tmp = 0; tmp < n; tmp++){
  d[tmp] = tmp;
}
do{
  hoge;
} while(next_permutation(d, d+n));

に置換されます．
他のもだいたい同様で，辞書順最小のものからループします．
（重複を許さない組合せで n より m のほうが小さい場合（条件を満たす配列が存在しない場合）は，ループの中身は1回も実行されません）
このループに使用する，next_permutation() に相当する，条件を満たす配列で，辞書順で次のものを求める関数 scomb(), mcomb(), sarr(), marr() 等もあり以下のとおりです．

hoge は rep_piyo の説明を参照．

特殊なループ2（主に2次元以上で一定以内の距離を走査するループ）

例から書くと

rep_dist(i, j, 3, 8) wtF("({i},{j})");
// (3,8)からマンハッタン距離で1以下の距離にある（(3,8)は除く）
// (2,8)(3,7)(3,9)(4,8)

rep_dist(i, j, k, 3, 8, 1) wtF("({i},{j},{k})");
// (3,8,1)からマンハッタン距離で1以下の距離にある（(3,8,1)は除く）
// (2,8,1)(3,7,1)(3,8,0)(3,8,2)(3,9,1)(4,8,1)

rep_dist(i, j, 3, 8, m2z) wtF("({i},{j})");
// (3,8)からマンハッタン距離で2以下の距離にある（(3,8)自身も含む）
// (1,8)(2,7)(2,8)(2,9)(3,6)(3,7)(3,8)(3,9)(3,10)(4,7)(4,8)(4,9)(5,8)

rep_dist(i, j, 3, 8, t2) wtF("({i},{j})");
// (3,8)からチェビシェフ距離で2以下の距離にある（(3,8)は除く）
// (1,6)(1,7)(1,8)(1,9)(1,10)(2,6)(2,7)(2,8)(2,9)(2,10)(3,6)(3,7)(3,9)(3,10)(4,6)(4,7)(4,8)(4,9)(4,10)(5,6)(5,7)(5,8)(5,9)(5,10)    

rep_dist(i, j, 3, 8, e3) wtF("({i},{j})");
// (3,8)からユークリッド距離で3以下の距離にある（(3,8)は除く）
// (0,8)(1,6)(1,7)(1,8)(1,9)(1,10)(2,6)(2,7)(2,8)(2,9)(2,10)(3,5)(3,6)(3,7)(3,9)(3,10)(3,11)(4,6)(4,7)(4,8)(4,9)(4,10)(5,6)(5,7)(5,8)(5,9)(5,10)(6,8)

rep_dist(i, j, 3, 8, ee2) wtF("({i},{j})");
// (3,8)からユークリッド距離でsqrt(2)以下の距離にある（(3,8)は除く）
// (2,7)(2,8)(2,9)(3,7)(3,9)(4,7)(4,8)(4,9)

一般的には

という形式です．
x1,...,xk がループ変数（定義されてなければint型で勝手に定義します）で，c1,...,ckが中心の座標を表します．

modeは以下を連結したものを指定します：

距離の定義は以下の通りです：

距離を指定する場合，あまり大きな整数を指定することは考えてません（バグったり不具合が起こる可能性が高いです）．
ループの順番は辞書順で回るはずです．

演算子

昔のGCC拡張で存在した <? および >? 演算子の同時に代入するバージョンのみ使えます．
つまり，a <?= b; は a = min(a, b); と，a >?= b; は a = max(a, b); と大体同じです．
代入しないバージョンは素直にminおよびmaxを使うこと．
a >?= b > 10 は a >?= (b > 10) とみなされます．必要なら (a >?= b) > 10 などと括弧を付けてください．
（式 a >?= b の評価値は代入後の a の値，つまり max(a,b) です）

正の整数に関する繰り上げの割り算演算子 /+ が使えます．
13 /+ 3 は 5 となります．
実際には a /+ b は (a+b-1) / b で定義され，正の整数でないと繰り上げ割り算になる保証はありません．
また，a+b-1 がオーバーフローする可能性があるので要注意です．
a = a /+ b; は a /+= b; と書くこともできます．
a /+= b > 10 は a /+= (b > 10) とみなされます．必要なら (a /+= b) > 10 などと括弧を付けてください．
負などもありうる場合には以下の関数が使えます．

負の数を正の数で割った余りを非負の数で返す %% 演算子があります．
(-5) %% 2 は 1 になります．
演算子の優先順位が低いので，-5 %% 2 は-(5 %% 2) = -1になります．
a = a %% b; は a %%= b; と書くこともできます．
a %%= b > 10 は a %%= (b > 10) とみなされます．必要なら (a %%= b) > 10 などと括弧を付けてください．

べき乗演算子 ** が使えます．
2 ** 3 は $2^3 = 8$ を表します．
点 (x1, y1) と (x2, y2) とのユークリッド距離は sqrt( (x1-x2)**2 + (y1-y2)**2 ) と簡潔に書けるようになります．
バイナリ法を使用します．
x ** y において，y は非負整数である必要があって，結果の型は x の型と同じになります（y が非負整数じゃない場合は標準の pow 関数などを使って下さい）．
ただし，x, y ともに double 型のときは，標準の pow(x,y) が呼び出されます．
a = a ** b; は a **= b; と書くこともできます．
a **= b > 10 は a **= (b > 10) とみなされます．必要なら (a **= b) > 10 などと括弧を付けてください．

数値の後の掛け算の演算子*は省略できることがあります．
z = 2 2x+2(x+5); で z = 2 * 2 * x + 2 * (x+5); の意味になります．
他の解釈ができる場合は*を省略できません．
2u は 2*u ではなくunsigned 型の定数 2 で，3d1 は 3*10 = 30 を表す整数で 3 * d1 などにはなりません．
数値はアルファベットで終わっている場合は，*を（現状では）省略できません．
z = 2u x; は駄目です．
また，数値の後以外の*の省略は（現状では）できません．
例えば，x(x+y) や (2)(x+y) に * が補われることはありません．
また，単純に*が補われるだけなので，x=2 のときに 7%2x は 7%2*x=1*2=2 となることに注意してください（7%(2x)ではない）．

等式，不等式の条件を続けるときに && を省略できます．
if(5 < x+y < 10) は if(5 < x+y && x+y < 10) に置き換わります．
if(i <= 5 < k <= 12 > j != m == n) は if(i <= 5 && 5 < k && k <= 12 && 12 > j && j != m && m == n) に置き換わります．
if(5 < x++ < 10) は if(5 < x++ && x++ < 10) に置き換わるので注意してください．
ただし，hoge < hoge > hoge < hoge > hoge などの場合は，テンプレート絡みなどで使用することがあるので，展開されません（左から右に単調非減少の形で条件を書くと良いと考えています）．

複数の演算（内部でarraylike operationと呼んでるもの）

(a1,a2,...,an) += (b1,b2,...,bn); のような形で複数の演算を一度に行います．
コンマ演算子をオーバーロードしていると変なことが起こるかもしれないので，この機能を無効化する場合は //no-arraylike-operations のフラグを指定してください．
具体的には，

(a,b) = (b,a+b);

は

{
  auto tmp1 = b;
  auto tmp2 = a+b;
  a = tmp1;
  b = tmp2;
}

と展開され，

(a,b) += k;

は

{
  auto tmp = k;
  a += k;
  b += k;
}

と展開されます．
また，(a,b,c)++; や --(a,b); はそれぞれ a++; b++; c++; や --a; --b; に展開されます．
更に，現状では

(a, b, c) *= (f(m, n) + k * (b, c, a) + (s, t)) % 100;

は

{
  auto tmp1 = (f(m, n) + k * b + s) % 100; // 実際は s とかは (s) とカッコが付いたりします
  auto tmp2 = (f(m, n) + k * c + t) % 100; 
  auto tmp3 = (f(m, n) + k * a + s) % 100; 
  a *= tmp1;
  b *= tmp2;
  c *= tmp3;
}

に展開されます．
共通部分は (hoge, piyo) の形式で書かなければ良いです．
また，サイズが違う場合はサイクリックに適応されます（R言語のような感じ）．
現状では，f(n)が3回呼び出されますが，将来的に変更される可能性があります（右辺に副作用があるものを書かないでください）．

複数の処理（内部でarraylike sentenceと呼んでるもの）

arraylike operationのある種の一般化です．
@[a,b] と@[]内に,で区切ったものが展開されます．

unionFind u_a, u_b, u_c;
u_@[a,b,c].walloc(10,1);

で

unionFind u_a, u_b, u_c;
u_a.walloc(10,1);
u_b.walloc(10,1);
u_c.walloc(10,1);

に展開されます．
また，

unionFind u_a, u_b, u_c;
u_@[a,b,c].walloc(@[10,20,30],1);

で

u_a.walloc(10,1);
u_b.walloc(20,1);
u_c.walloc(30,1);

に展開されます．
中身の要素の長さが違う場合は，短いものはR言語っぽくサイクリックに拡張されます．
また，2種類以上，独立に展開する場合は，@1[a,b]，@2[a,b]と@+数字1文字で11種類使えます．

u_@1[a,b,c].walloc(@2[10,20,30],1);

は

u_a.walloc(10,1);
u_b.walloc(10,1);
u_c.walloc(10,1);
u_a.walloc(20,1);
u_b.walloc(20,1);
u_c.walloc(20,1);
u_a.walloc(30,1);
u_b.walloc(30,1);
u_c.walloc(30,1);

など（順番は不定にしておきます）に展開されます

定数

int_inf は 1073709056 ($2^{30}-2^{15}$) に，
ll_inf は 4611686016279904256LL ($2^{62}-2^{31}$) に，
double_inf は 1e150 に置換されます．

int_inf および ll_inf はそれぞれ2倍してちょっとした数を足してもint型，long long型でオーバーフローしないという値に設定しています．
また，double_inf は2乗してもオーバーフローしないという値に設定しています．

また，MDは1000000007（$10^9+7$）に，PIは3.14159265358979323846（円周率）に置換されます（厳密には最初に#define MD 1000000007などが追加されます）．
MDとPIはコード中で #define MD 1000000009 などと言う記述が出てきたら置換されずそちらが優先されます．

また，double型の定数の書き方 1e-5 などと同様に，整数型の定数を 1d5 などと書けます．
$x$d$y$ で $\lfloor x \times 10^y \rfloor$ を表します．
$2^{31}$ 未満であれば int 型，$2^{31}$ 以上であれば ll 型，$2^{63}$ 以上であれば ull 型の定数になり，$2^{64}$ 以上の値だと上手く動きません．
$y$ は整数で $-30$ 以上 $30$ 以下でないと正しく動きません．

関数のメモ化

関数の引数に続いて : で区切ってMemoizeをつけると，同じ引数で呼び出されたとき，以前に計算した結果を即座に返すようにします．
引数が配列（ポインタ）とか変なのを含む場合は動かないと思います．

Modint f(int n : Memoize){
  if(n<=1) return n;
  return f(n-1) + f(n-2);
}

でフィボナッチ数を計算する関数をメモ化します．
標準では map を使用してメモするため，f(n) を呼び出したとき，この場合は，O(n log n) 時間，O(n) 領域使うと思います．
f(n) を計算するときに，直接的，または，間接的に f(n) を呼び出すと動きません（多分無限ループ）．

配列にメモする場合は，

Modint f(int n : Memoize[1d5]){
  if(n<=1) return n;
  return f(n-1) + f(n-2);
}

とすると，n が 0 から 99999 (=10^5-1) しか呼び出さないことを仮定して Modint memo[1d5]; を用意してメモ化します．
0から始まらない場合

Modint f(int n : Memoize[-3:123]){
  if(n<=1) return n;
  return f(n-1) + f(n-2);
}

で n が -3 以上 123 以下と仮定して Modint memo[127]; を使ってメモ化します（127 = 123 - (-3) + 1）．
2次元以上の場合は，範囲を,で区切って書きます．

Modint f(int x, int y : Memoize[-1:10,15]){
  hoge
}

は x が -1 から 10 まで，y は 0 から 14 までの範囲と仮定してメモ化します．

計算結果を消去したい場合は f_clear() を呼び出して下さい（現状全部消えます，配列の場合，サイズに比例した時間がかかります）．
fは元々の関数名で，対応するものに変更してください．

ワーキングメモリ

ワーキングメモリを必要な関数や機能などを使うと勝手にワーキングメモリを確保します．
void *wmem; に（デフォルトで）96,000,000バイトのメモリが確保されます．
サイズを変更する場合は，どこか（の行頭）で，
//working_memory=500MB
などと書くと500*1024*1024バイトのメモリになります．
//working_memory=500m
//working_memory=524288000
も同じ意味です．Bは省略可能，K,M,Gが接頭語として使えます．

行列

行列は Matrix<mint> m; などで定義します．
m[0][1] で0行1列の成分にアクセスできます（行番号，列番号は0から始まる）．
行列の足し算，引き算，かけ算は+，-，*でできます．べき乗演算子 ** なども使えます．定義できない演算をすると0行0列の行列になります．
int, ll, doubleの定数倍も可能です．
m = 1; などと定数を代入すると対角成分が1に，それ以外は0になります．
以下は Matrix<T> に関してです．

コンストラクタ

その他

置換

置換は Permutation p; などで定義します．
p[i] = j は第i要素を第j番目に飛ばす，という意味です．
i も j も 0-origin です．
現状 p ** n の計算は（他の型と同様に）バイナリ法です．

コンストラクタ

デストラクタ

演算子

メンバ関数

{
  int A[10] = {5,2,8,9,1,1,100,800,9,10};
  int B[10];
  int sz;
  int pp1[10] = {1,2,3,4,5,6,7,8,9,0};
  int pp2[10] = {1,0,3,2,5,4,7,6,9,8};

  Permutation p1, p2, m, id;
  p1.changeSize(10);
  p2.changeSize(10);
  rep(i,10) p1[i] = pp1[i];
  rep(i,10) p2[i] = pp2[i];



  wt(A(10));           // 5 2 8 9 1 1 100 800 9 10
  p1.apply(A, B);
  wt(B(10));           // 10 5 2 8 9 1 1 100 800 9
  p2.apply(A, B);
  wt(B(10));           // 2 5 9 8 1 1 800 100 10 9



  m = p1 ** 13;
  m.apply(A, B);
  wt(B(10));           // 800 9 10 5 2 8 9 1 1 100



  m = p1 * p2;
  m.apply(A, B);
  wt(B(10));           // 9 2 5 9 8 1 1 800 100 10

  p2.apply(A);
  p1.apply(A);
  wt(A(10));           // 9 2 5 9 8 1 1 800 100 10


  id.changeSize(10);
  id = 1;              // identity
  rep(i,100){
    m = p1 ** i;
    if(m==id) wt(i);   // i = 0, 10, 20, ..., 90
  }
  rep(i,100){
    m = p1 ** i;
    if(m==p1) wt(i);   // i = 1, 11, 21, ..., 91
  }


  sz = p1.cycle_len(B);
  wt(B(sz));              // 10
  sz = p2.cycle_len(B);
  wt(B(sz));              // 2 2 2 2 2
  sz = id.cycle_len(B);
  wt(B(sz));              // 1 1 1 1 1 1 1 1 1 1
}

IntMap

{0,1,...,n-1} から {0,1,...,n-1} の写像は IntMap f; などで定義します．
f[i] = j は第i要素を第j番目に飛ばす，という意味です．

コンストラクタ

デストラクタ

演算子

メンバ関数

変数

変数（多分使わない）

Fenwick Tree (Binary Indexed Tree, BIT)

（1次元の）Fenwick treeが使えます．
fenwick<int> t; などで定義します．この場合は各要素や和などを求める時に全てint型で計算されます．
扱う配列の長さの最大値を maxN として，t.malloc(maxN); または t.walloc(maxN); でメモリを確保します．
その後，配列の長さが N の場合に初期化（全要素を0にする）場合，t.init(N); とします．
メモリ確保とともに，確保したメモリ分の長さを初期化する場合は，t.malloc(N, 1); または t.walloc(N, 1); です．

関数などは以下の通り（fenwick<T> t; で宣言したとします．また，要素数を $N$ として，0番目の要素から$N$-1番目の要素まで存在します）：

区間は閉区間 [a,b] の形で指定することに注意して下さい．

malloc()を使った場合のメモリの開放は t.free(); です．

  {
    int d[10] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 4};
    int arr[20];
    int i, s;

    fenwick<int> t;
    t.walloc(10);
    t.init(10);
    rep(i,10) t.add(i,d[i]);

    s = t.get(3);
    wt(s); // d[0]+d[1]+d[2]+d[3] = 3+1+4+1 = 9
    s = t.range(5,7);
    wt(s); // d[5]+d[6]+d[7] = 9+2+6 = 17

    rep(i,20) arr[i] = t.kth(i);
    wt(arr(20)); // 0がd[0]個，1がd[1]個，…からなる配列のk番目の要素
                 // 0 0 0 1 2 2 2 2 3 4 4 4 4 4 5 5 5 5 5 5
  }

演算を + ではなく ^ にしたバージョンは fenwick_xor<T> です．
基本的な機能は同じですが，kth() がありません．

バイナリヒープ（priority_queueとほぼ同様）

Heap<T> h; もしくは Heap_max<T> hm; で宣言する．
Heapは通常の最小値を取り出せるやつ，Heap_maxは最大値を取り出せるやつ．
大体の操作は $O(\log size)$．

Heap<T> h; について：

Heap_max<T> hm; について：

バイナリヒープ（固定長配列用）

LHeap<int> などで宣言．
$N$ 要素の配列 $A_k = \verb|val[k]|$ を考える．
ヒープにある要素を入れたり値を変えたり（$\verb|change|$），ヒープの中に入っている最小の要素を取り出して取り出した要素の番号を返したり（$\verb|pop|$）する．
大体の操作の計算時間 $O(\log N)$．
以下は LHeap<T> h; で定義したとする．

よく使いそうなもの：

そうではないもの：

  int i;
  double v;
  LHeap<double> hp;

  hp.walloc(10);
  hp.init(10);

  hp.change(0, 100.0);
  hp.change(1, 200.0);
  hp.change(8, 80.0);
  hp.change(1, -200.0);
  hp.change(8, 150.0);

  while(hp.size){
    i = hp.pop();   // 1 -200.000000000000000
    v = hp.val[i];  // 0 100.000000000000000
    wt(i,v);        // 8 150.000000000000000
  }

バイナリヒープ（ダイクストラ用）

DijkstraHeap<int> などで宣言．
バイナリヒープ（固定長配列用）のダイクストラ用にチューニングしたもの．
$\verb|pop|$ した時に $\verb|visited[]|$ のフラグを立てる，更新時に訪れたものや長くなったものは更新しないなどを関数の中で判定する．

よく使いそうなもの：

そうではないもの：

  int i;
  double v;
  DijkstraHeap<double> hp;

  hp.walloc(10);
  hp.init(10);

  hp.change(0, 100.0);
  hp.change(1, 200.0);
  hp.change(8, 80.0);
  hp.change(1, -200.0);
  hp.change(8, 150.0);

  while(hp.size){
    i = hp.pop();   // 1 -200.000000000000000
    v = hp.val[i];  // 8 80.000000000000000
    wt(i,v);        // 0 100.000000000000000
  }

セグメントツリー（標準的なの？）

（1次元の）セグメントツリーが使えます．
segtree<int> t; などで定義します．この場合は各要素や和などを求める時に全てint型で計算されます．
1回のみ使用する場合は，配列の長さを N として t.malloc(N, 1); とすると，配列の要素が全て 0 で初期化され，セグメントツリーが使えるようになります．
何回も使いまわす可能性がある場合は，配列の長さの最大値を maxN として，t.malloc(maxN); でメモリを確保します．
その後，配列の長さが N の場合にセグメントツリーを使えるようにするためには，t.setN(N); で使えるようになります．
mallocの代わりにwallocでワーキングメモリを使ってメモリを確保します．

0以外で初期化したい場合は，t.setN(N,0,0);（各要素は全く初期化されない），または，t.setN(N,1,0); （各要素は一応0で初期化される）としておき，
t[hoge] = 要素hogeの初期値;
と適当に初期化した後，t.build();とすれば使えるようになります．

segtree<T> t; とした場合，使える感じの関数は以下の通り（要素数を $N$ として，0番目の要素から$N$-1番目の要素まで存在します）：

区間は最初は含むが最後は含まない [a,b) の形で指定することに注意して下さい．

malloc()を使った場合のメモリの開放は t.free(); です．

セグメントツリー（亜種？）

初期化の仕方などは標準的な segtree と同じですが，機能が制限されていたり，変な機能がついているものです．
基本的に必要な機能のみがついているものを使うと，速くて省メモリのはずです．
基本的に構造体の名前が segtree_[変更に対する対応クエリの羅列]_[取得に関する対応クエリの羅列] という形式になっています（長い…）．
例えば，
segtree_Point_SumMin<T> t;
だと，変更に関するクエリの
void t.add(int x, T val)
void t.change(int x, T val)
と取得に関するクエリの
T t.getSum(int a, int b)
pair<T, int> t.getMin(int a, int b)
T t.getMinVal(int a, int b)
int t.getMinInd(int a, int b)
が使用できます．

変更に関するクエリと構造体の名前に含まれていたら使用できるという文字列（,で区切られている場合どれかが含まれていれば使用可能）

取得に関するクエリと構造体の名前に含まれていたら使用できるという文字列（,で区切られている場合どれかが含まれていれば使用可能）

定義されている構造体

その他の事項：
segtree_ChangeAdd_SumMin は通常の segtree を使ってください．
segtree_Point_Sum（1点更新で和を求めるだけのもの）はfenwickでできます（が，t.change(int x, T val) に対応するには値を配列などに保持し，差分を足してください）．

セグメントツリー（1点更新の汎用的なの）

segtree_ph<T> t; で定義します．
初期化は通常のsegtreeと同じですが，0で初期化するように指定しても初期化されません（同じように書けるように引数は存在します）．

res = f(a, b) を計算する関数
T segtree_ph_func(T a, T b){ hoge; }
をグローバルで定義しておきます．fは結合律 f(a,f(b,c)) = f(f(a,b),c) =: f(a,b,c) を満たすとします．

例えば，T = int で，
int segtree_ph_func(int a, int b){ return a + b; }
を作っておくと，1点更新で，区間和を求めることができるsegtreeになります．

ただし，基本的には，汎用的に利用するため，構造体と関数を新しく定義して利用することを想定しています．
実装方法は以下も参考にしてください．
Codeforces Round #672 DIV2 C2問題 - Pokemon Army (hard version)

セグメントツリー（1点更新の汎用的なの，旧版）

segtree_phとの違いは segtree_p*_func の形式です．

segtree_pg<T> t; で定義します．
初期化は通常のsegtreeと同じですが，0で初期化するように指定しても初期化されません（同じように書けるように引数は存在します）．

res = f(a, b) を計算する関数
void segtree_pg_func(T &res, T &a, T &b){ hoge; }
をグローバルで定義しておきます．fは結合律 f(a,f(b,c)) = f(f(a,b),c) =: f(a,b,c) を満たすとします．

例えば，T = int で，
void segtree_pg_func(int &res, int a, int b){ res = a + b; }
を作っておくと，1点更新で，区間和を求めることができるsegtreeになります．

ただし，基本的には，汎用的に利用するため，構造体と関数を新しく定義して利用することを想定しています．
実装方法は以下も参考にしてください．
Codeforces Round #672 DIV2 C2問題 - Pokemon Army (hard version)

segtree_pg 名前の由来は p は1点更新を意味する point，g はグローバルに関数を定義する形式から名前をつけています．

セグメントツリー（区間更新の汎用的なの）

segtree_rh<SVAL, SFUN> t; で定義します．
初期化は通常のsegtreeと同じですが，0で初期化するように指定しても初期化されません（同じように書けるように引数は存在します）．

res = h(a, b) を計算する関数
SVAL segtree_rh_merge(SVAL a, SVAL b){ hoge; }
をグローバルで定義しておきます．hは結合律 h(a,h(b,c)) = h(h(a,b),c) =: h(a,b,c) を満たすとします．

変更に関して，res = f(a) を計算する関数
SVAL segtree_rh_apply(SFUN f, SVAL a){ hoge; }
および，関数の合成 res(x) = f(g(x)) なる関数 res を計算する関数
SFUN segtree_rh_compose(SFUN f, SFUN g){ hoge; }
をグローバルで定義しておきます．

AtCoder Libraryのlazy_segtreeとだいたい同じ機能です．実装方法は例えば以下を参考にしてください．
AtCoder Library Practice Contest K問題 - Range Affine Range Sum
AtCoder Library Practice Contest L問題 - Lazy Segment Tree
Codeforces Round #684 DIV1 C問題 - Greedy Shopping (二分探索の参考)

また，changeでは全て一定値で置き換え，getで最小値を取得の場合は，segtree_rh<ll, ll> で，
ll segtree_rh_apply(ll f, ll a){ return f; }
ll segtree_rh_merge(ll a, ll b){ return min(a, b); }
ll segtree_rh_compose(ll f, ll g){ return f; }
などでできますが，複雑になると構造体を作ったほうがわかりやすい気がします．

セグメントツリー（区間更新の汎用的なの，旧版）

segtree_rh との違いは segtree_rg_func の関数名，関数の形式の違いと，恒等写像を用意する必要があるところです．

segtree_rg<SVAL, SFUN> t; で定義します．
初期化は通常のsegtreeと同じですが，0で初期化するように指定しても初期化されません（同じように書けるように引数は存在します）．

res = h(a, b) を計算する関数
void segtree_rg_func(SVAL &res, SVAL a, SVAL b){ hoge; }
をグローバルで定義しておきます．hは結合律 h(a,h(b,c)) = h(h(a,b),c) =: h(a,b,c) を満たすとします．

変更に関して，res = f(a) を計算する関数
void segtree_rg_func(SVAL &res, SFUN f, SVAL a){ hoge; }
および，関数の合成 res(x) = f(g(x)) なる関数 res を計算する関数
void segtree_rg_func(SFUN &res, SFUN f, SFUN g){ hoge; }
をグローバルで定義しておきます．
また，恒等写像を表す写像 res を返す
void segtree_rg_id(SFUN &res)
もグローバルで定義しておきます．

SVAL, SFUN を同じ型にすることは現状できません．
基本的には，汎用的に利用するため，構造体と関数を新しく定義して利用することを想定しています．

AtCoder Libraryのlazy_segtreeとだいたい同じ機能です．実装方法は例えば以下を参考にしてください．
AtCoder Library Practice Contest K問題 - Range Affine Range Sum
AtCoder Library Practice Contest L問題 - Lazy Segment Tree

また，changeでは全て一定値で置き換え，getで最小値を取得の場合は，segtree_rg<int, ll> で，
void segtree_rg_id(ll &res){ res = ll_inf; }
void segtree_rg_func(int &res, ll f, int a){ res = if[f==ll_inf, a, f]; }
void segtree_rg_func(int &res, int a, int b){ res = min(a, b); }
void segtree_rg_func(ll &res, ll f, ll g){ res = if[f==ll_inf, g, f]; }
などでできますが，構造体を作る余裕があるなら作ったほうがわかりやすい気がします．

segtree_rg 名前の由来は r は区間更新を意味する range，g はグローバルに関数を定義する形式から名前をつけています．

static segment tree

segment treeではないです（segment treeと同じインターフェースで利用できるようにしています）．
範囲に足し算するのは差分を2箇所操作する，和を求めるには累積和を事前計算しておくなどして，
変更クエリ・取得クエリのみを続けて行う際は，最初の1回除きできるだけ効率よく計算できるようにします．
変更クエリと取得クエリを繰り返して行うと性能が劣化します．
セグメントツリー（亜種？）と同様の形式です．
定義されている構造体

参考：LeetCode Weekly Contest 217 3問目 - Minimum Moves to Make Array Complementary [1674]

2次元領域木，2d range tree

2次元平面内の長方形領域に含まれる点の重みの和を求める．
rangeTree2d<S,T1,T2> t; で定義する．
Sは重みの型，T1は1次元目（x座標）の型，T2は2次元目（y座標）の型．
実装は現状，y座標の区間を扱うようなsegment treeで，各ノードには対応するx座標値をソートして保持，x座標の区間の重みを計算できるようにFenwick treeを保持．
領域量は O(N log N) でワーキングメモリを結構使うので注意．必要ならば，//working_memory=300m などしておくと良い．

重みが一様（全て1）のバージョン rangeTree2d_nw もあります．nwはnon-weightedのつもり．
rangeTree2d_nw<T1,T2> t; で定義する．

2次元領域木，2d range tree（抽象化版）

2次元平面内の長方形領域に含まれる点の重み w1, w2, ..., wn に対して f(w1, w2, ..., wn) を求める（可換かつモノイド）．
rangeTree2d_pf<S,T1,T2> t; で定義する．
領域量は O(N log N) でワーキングメモリを rangeTree2d 以上に使うので注意（Fenwick treeの代わりにSegment treeで管理します）．必要ならば，//working_memory=300m などしておくと良い．

関数 f を表す関数
S rangeTree2d_pf_func(S a, S b)
をグローバルに定義しておいてください．
例えば，rangeTree2d_pf<int,int,int> t; において，最小値を求める場合は，

int rangeTree2d_pf_func(int a, int b){
  return min(a,b);
}

とすれば良く，この場合は t.setDefault(int_inf) などを呼び出しておくと良いです．

f(x,y,z,w) = f(x,f(y,f(z,w))) みたいに計算されます．

グラフ（構造体）

graph構造体を使えます．graph g; などで定義します．

無向木に対する全方位DP（Rerooting）

wgraphにあるRerootingでECostがなくなって，関数の名前の最初にwがなくなったものです．
wgraphのほうの説明を見てください．

例えば，グローバルに
struct rval{ int sz; ll dist; };
void RerootingId(rval &a){ a = {0, 0}; }
rval RerootingMerge(rval a, rval b){ return {a.sz + b.sz, a.dist + b.dist}; }
rval RerootingEdge(rval a, int EFrom, int ETo){ return a; }
rval RerootingNode(rval a, int Nind){ return {a.sz+1, a.dist+a.sz}; }
を用意しておくと，
szにそのノードを根とする部分木のノード数＝全体のノード数
distにそのノードから他のノードまでの距離の総和
を求めることになります．

{
  int N = 6, M = 7;                       //  0 → 1 ← 2
  int A[7] = {0, 0, 1, 2, 3, 4, 5};       //  |    ^    |
  int B[7] = {1, 3, 2, 5, 4, 1, 4};       //  v    |    v
                                          //  3 → 4 ← 5
  int i;
  graph g;
  int dist[6];

  g.setEdge(N, M, A, B);                  // node 0: degree 2: 1 3
  rep(i,N){                               // node 1: degree 3: 0 2 4
    wtF("node {i}: degree {g.es[i]}: ");  // node 2: degree 2: 1 5
    wt(g.edge[i](g.es[i]));               // node 3: degree 2: 0 4
  }                                       // node 4: degree 3: 3 1 5
                                          // node 5: degree 2: 2 4
  g.getDist(3, dist);
  wt(dist(N));            // 1 2 3 0 1 2

  g.setDirectEdge(N, M, A, B);            // node 0: degree 2: 1 3
  rep(i,N){                               // node 1: degree 1: 2
    wtF("node {i}: degree {g.es[i]}: ");  // node 2: degree 1: 5
    wt(g.edge[i](g.es[i]));               // node 3: degree 1: 4
  }                                       // node 4: degree 1: 1
                                          // node 5: degree 1: 4
  g.getDist(3, dist);
  wt(dist(N));            // -1 2 3 0 1 4
}

枝に重みのあるグラフ（構造体）

wgraph構造体を使えます．wgraph<T> g; などで定義します．

無向木に対する全方位DP（Rerooting）

枝は向きがあると思います（向きによって重みが違っても良いですが，無向木に対して枝を両方の向きに分裂させた形のグラフのみが対象です）．
ノードkに対する値(型はV)をn(k)，枝kに対する値(型はV)をe(k)と書くことにします．
枝kに対する値は，枝kの重み(g.cost)がECost，枝kはEFromからEToに向かう枝として，e(k) = wRerootingEdge(n(Eto), ECost, EFrom, ETo) で定義されます．

ノードkに対する値は，ノードkから他のノードに向かう枝をe1, e2, ..., em としたとき，
tmp = f(e1, e2, ..., em)
として
n(k) = wRerootingNode(tmp, k)
で定義します．
ただし，f は f(a, b, c) = f(a, f(b, c)) = f(f(a, b), c) などを満たし，更に（現状は）可換と仮定します．
fを表す関数を wRerootingMerge で指定します．
また，f(e, a) = a なる単位元 e を設定する関数 wRerootingId も用意しておきます．

最終的には，全ノードに対する n(k) の値を res[k] に代入して返します．

例えば，グローバルに
struct rval{ int sz; ll dist; };
void wRerootingId(rval &a){ a = {0, 0}; }
rval wRerootingMerge(rval a, rval b){ return {a.sz + b.sz, a.dist + b.dist}; }
rval wRerootingEdge(rval a, T ECost, int EFrom, int ETo){ return {a.sz, a.dist + a.sz * ECost}; }
rval wRerootingNode(rval a, int Nind){ return {a.sz+1, a.dist}; }
を用意しておくと（Tはintを想定，wgraph<T>の場合），
szにそのノードを根とする部分木のノード数＝全体のノード数
distにそのノードから他のノードまでの距離の総和（costが距離を表します）
を求めることになります．

Heavy-Light Decomposition（HLD，重軽分解）

根付き無向木に対してHeavy-Light Decomposition（HLD）を計算します．
根はノード0を利用します．
計算したHLDを用いて，LCAなどを高速に求めることができます．
また，segtreeを載せることができます．
HLD hld; で定義したとします．

以下 HLD hld; の多分使わない情報．

Fenwick treeを載せるときは，HLD_fenwick<T> t; を定義します．
ノードに値を持ちます．
（枝に値をもたせたい場合は，すぐ上に向かう枝の値をノードに持たせて，LCAでパスを分割したりするとできるかも）

以下 HLD_fenwick<T> t; の多分使わない情報．

segtreeを載せるときは，HLD_segtree<T> t; を定義します．
ノードに値を持ちます．

枝に重みが載っていると思った場合の関数は以下の通り（実際は枝(x,y)の重みはx,yの内，深い方のノードに持たせていて，内部でLCAやら色々呼び出して辻褄合わせたりするので多分遅め）．参考：第四回 アルゴリズム実技検定 M問題 - 筆塗り．

以下 HLD_segtree<T> t; の多分使わない情報．

最大流（maxflow, Dinic）

最大流は maxflow<int,ll> flow; などで定義します．この場合，各辺の流量は int 型ですが，合計で流れる流量は ll 型です．
以下の説明では maxflow<T,S> flow; とします．

以下のコードは http://www.spoj.com/problems/FASTFLOW/ を解くコード．

int A[30000], B[30000], C[30000];
{
  int N, M;
  ll res;
  maxflow<int,ll> f;

  rd(N,M);
  rd((A,B,C)(M));
  A[0..M-1]--;
  B[0..M-1]--;

  f.malloc(N);
  f.init(N);
  f.addEdge(A[0..M-1],B[0..],C[0..],C[0..]);
  res = f.solve(0, N-1);
  wt(res);
}

最小費用流（minCostFlow）

最大流は minCostFlow<int,double> flow; などで定義します．この場合，流量は int 型で，コストは double 型です．
以下の説明では minCostFlow<FT,CT> flow; とします．
徐々に流していくアルゴリズムを適当に実装したもので，少なくても現状は良い実装ではないと思います．
負の閉路などがあると動きません．

参考：yukicoder No.1288 - yuki collection

Trie

Trie t; で定義したとします．
最終的なノード数の上限を n（例えば食わせる文字列の文字数の和+1），アルファベットのサイズ（文字の種類数）を k として，t.malloc(n, k); などでメモリの確保 + 初期化します．
n=10^6, k=26 で100メガバイト以上メモリが必要なので注意してください（nk*sizeof(int)は最低限必要で，それ以外も細々と必要かも）．
ルート（空文字）に対応するノード番号は 0 です．

AhoCorasick

AhoCorasick aho; で定義したとします．
最終的なノード数の上限を n（例えば食わせる文字列の文字数の和+1），アルファベットのサイズ（文字の種類数）を k として，aho.malloc(n, k); でメモリの確保＋初期化します．
アルファベットは0からk-1までの数値です．
文字列を addWord でいくつか加えてTrieぽいグラフを作る．
そして，construct で failedリンクを作って準備完了です．

全ての文字列を区別する必要がなければ以下のもので十分かもしれません．

AhoCorasick_Sum<S> aho; で定義したとします．
最終的なノード数の上限を n（例えば食わせる文字列の文字数の和+1），アルファベットのサイズ（文字の種類数）を k として，aho.malloc(n, k); でメモリの確保＋初期化します．
アルファベットは0からk-1までの数値です．
文字列を addWord でいくつか加えてTrieぽいグラフを作る．
そして，construct で failedリンクを作って準備完了です．

AhoCorasickの使い方の参考：
AtCoder Beginner Contest #122 D問題 - We Like AGC

Polynomial（1変数多項式）

あまりちゃんと作っていません．
Polynomial<T> P; で作ります．定義域，値域ともにTです．
疎構造ではないので，次数の高い多項式は問答無用でたくさんの項を扱うことになって遅いです．
今のところ愚直な実装です．

コンストラクタ

デストラクタ

その他関数 [メンバ関数]

オペレーター [メンバ関数]

オペレーター [メンバ関数以外]

使わなさそうなの

  double x;
  Polynomial<double> P, Q, R1, R2; // P = Q = 0

  P.change(2, 1); // P = x^2
  P.change(1, 2); // P = x^2 + 2*x
  P.change(0, 1); // P = x^2 + 2*x + 1

  x = P(2); // P(2) = 2^2 + 2*2 + 1 = 9

  Q.change(1, 1); // Q = x
  Q.change(0, 4); // Q = x + 4

  // x^2 + 2*x + 1 = (x-2) (x+4) + 9
  R1 = P / Q;  // x - 2
  R2 = P % Q;  // 9

  Q *= 2.0; // 2x + 8

  // x^2 + 2x + 1 = (0.5x - 1) (2x + 8) + 9
  R1 = P / Q; // 0.5x - 1
  R2 = P % Q; // 9

  Q.change(1, 0); // Q = 8
  R1 = P / Q; // (1/8) x^2 + (1/4) x + (1/8);
  R2 = P % Q; // 0

その他色々な関数など

  int i, j;
  int *a, **m, **hoge;

  walloc1d(&a, 100);
  walloc2d(&m, 50, 100);

  rep(i,100) a[i] = i;
  rep(i,50) rep(j,100) m[i][j] = i+j;
                                 // ↓出力 *例* (sizeof(*a)=4の環境)
  printf("%p %d\n",a,a);         // 0x404040 4210752
  printf("%p %d\n",m,m);         // 0x4041d0 4211152
  printf("%p %d\n",m[0],m[0]);   // 0x404298 4211352
  printf("%p %d\n",m[1],m[1]);   // 0x404428 4211752

  malloc2d(&hoge, 50, 100);
  free2d(hoge);

  int *a;
  void *mem;

  mem = wmem;        // ワーキングメモリの先頭アドレスを覚えておく
  walloc1d(&a, 1d6); // 10^6要素の配列を確保
  /* 何かする */
  wmem = mem;        // ワーキングメモリの先頭アドレスを戻すことによって，配列aを解放

Rand構造体．乱数生成に使う．xorshift．
Rand rnd; で宣言したとして以下の通り．
何回か実行したとき，うまく種を設定しないと最初の数十回ぐらいは似た系列が出てくるので，気になる場合は，最初にgetを100回呼び出すなど空打ちすると良い．
一部仕様は未決定．
種を設定しない場合は，time(NULL)を使って設定．

以下は微妙に仕様を決めきれてない．

以下はそのうち実装予定でまだ作ってない

Timer 構造体．
時間を測るために使う．Timer timer; で宣言したとして以下の通り．gettimeofdayを使用する．

  int i;
  ll sum = 0;
  Timer timer;
  double tm;
  timer.set();
  rep(i,1,1d8) sum += 1d9 /+ i;
  tm = timer.get();
  wtF("time: {tm}, sum: {sum}\n"); // time: 0.678610086441040, sum: 19048729277

Timer2 構造体．
Timer2 timer; などで宣言して上記と同じように使用可能（Timer 構造体と使い方は全く一緒）．
std::chrono::high_resolution_clock::now() を使用する．

string S = "HoGe@Piyo";
wt(toLower(S).c_str());  // hoge@piyo
wt(toUpper(S).c_str());  // HOGE@PIYO

x if[c1,s1,c2,s2,e] y; は if(c1){ x s1 y; } else if(c2){ x s2 y; } else { x e y; } に展開される．(c1,s1)のペアはいくつ合っても良い．eは空なら省略可能．
ただし，現状if文などの()の中では使用不可能．
例えば

  a[i] = x if[i%2==0,+,-] y;
  s[i] = b[i] if[i,+s[i-1]];

は以下のように展開されます：

  if(i%2==0){
    a[i] = x + y;
  } else {
    a[i] = x - y;
  }
  if(i){
    s[i] = b[i] + s[i-1];
  } else {
    s[i] = b[i];
  }

式に対して最小値，最大値，和などを求める．
最小値の場合は，
min[型][範囲](式)
の形式で [型] は省略可能（int型をたくさん足してll型で結果を得たい場合などは [型] を指定する）．
範囲を表す変数は int 型ですが，他の型の場合は範囲の書き方を見てください．
範囲が空なら，sumは0，mulは1，gcdは0，lcmは1になります．minは型が表せる最大の値，maxは型が表せる最小の値になります．

範囲の書き方は以下のとおりです．
各変数の動く範囲を,区切りで記述します（変数は定義されていなくても構いません，式の評価にのみ利用します）．
i=a---b : 変数 i を a から b まで（両端を含む）動かします．
i,a,b : 変数 i を a から b-1 まで（両端を含む）動かします．
(i,j)=a---b : 変数 i と j を a から b まで（両端含む）動かします．
(i,j),a,b : 変数 i と j を a から b-1 まで（両端含む）動かします．

変数の型を指定する場合は，変数名の前につけてください．
例えば (i,j),a,b において i は int 型だけど，j を ll 型にする場合は (i, ll j),a,b としてください．

型において「@ 条件」をつけると条件を満たすもののみ処理します．
また，「$ 値」をつけると範囲が空だったり，条件を満たすものが存在しない場合に，値を代入するようになります．
（値を指定しない場合は，それぞれの演算，型を考えて，単位元的なものを代入します）
min[i,0,n @ a[i] >= 10 $ 0](a[i])
で配列a[i]の中の10以上の要素の中での最小値を求めます．該当する要素がないなら0にします．
min[i,0,n @ a[i] >= 10](a[i])
の場合，a[i]がint型で該当する要素がないなら2147483647になります．

また，配列に対する argmin, argmax は以下の形式も使えます．

  {
    int i;
    i = min[k=1---100](abs(4*k-50));
    wt(i);                               // 2 と表示
    i = argmin[k=1---100](abs(4*k-50));
    wt(i);                               // 12 と表示
  }
  {
    int A[3][3] = {
      300000000, 500000000, 700000000,
      300000000, 200000000, 700000000,
      300000000, 500000000, 900000000
    };
    wt(min[i,0,3,j,0,3](A[i][j]) + max[i,0,3,j,0,3](A[i][j])); // 1100000000 = 200000000 + 900000000
    wt(sum[ll][i,0,3,j=0---2](A[i][j])); // 4400000000 (ll型なのでオーバーフローしない)
    wt(gcd[(i,j),0,3](A[i][j])); // 100000000
    wt(lcm[ll][(i,j),0,3](A[i][j])); // 63000000000
  }
  {
    wt(max[ll i,1d10,1d10+20](i+2)); // 10000000021
  }

それぞれ単調性が成り立たなければならない．
例えば，bsearch_minの場合，name=10のときcondが成り立つならば，name=10以上（maxval以下）のときもcondは成り立たなければならない．
typeは変数nameの型を指定し，float, doubleの場合は実数の二分探索，それ以外は整数の二分探索を行う．
bsearch_minでは，name=maxvalでは評価されず，name=maxvalより小さい場合に常に偽ならmaxvalが返ってくる（name=maxvalのときはblock, condが未定義になるようなものでも良い）．
今のところ，minval, maxvalは省略不可能．

optionは以下の通り．

実数の二分探索で，許容誤差を指定しない場合は，見ている範囲を[x,y]としたとき，(x+y)/2が（計算機上で）xまたはyに一致したら打ち切る（許容誤差を指定してもこの判定は行う）．

  int i, j, k, t;
  double x, y;

  k = -1;
  i = bsearch_max[int,k,0,100](k*k<=10);
  j = bsearch_min[int,k,0,100][
    t = 0;
    rep(j,1,k+1) t += k / j;
  ](t >= 100);
  x = bsearch_max[double,x,0,100](x*x<=10);
  y = bsearch_max[double,x,0,100,E=1e-1](x*x<=10);

  wt(i,j,k,x,y); // 3 28 -1 3.162277660168380 3.222656250000000

三分探索（内部実装は少し違うかも）のようなもの．二分探索とほぼ同様の書き方．

optionは以下の通り．

最小値を求める場合，name=kのときのeqの値を f(k) と書くことにしたら，とある L ≤ R が存在して
minval ≤ x < y ≤ L のとき f(x) > f(y),
L ≤ x < y ≤ R のとき f(x) = f(y),
R ≤ x < y ≤ maxval のとき f(x) < f(y)
が成り立たなければならない．

{
  wt(tsearch_min[ll,x,-1d9,1d9](x*(x+10)));                                 // -25
  wt(tsearch_argmin[ll,x,-1d9,1d9](x*(x+10)));                              // -5

  wt(tsearch_max[ll,x,-1d9,1d9,T=ll][ll y; y = x + 5;](-(y-5)*(y+5)));      // 25
  wt(tsearch_argmax[ll,x,-1d9,1d9,T=ll][ll y; y = x + 5;](-(y-5)*(y+5)));   // -5
}

参考：Codeforces Round #679 DIV1 C問題 - Solo mid Oracle

isPrime, Factor, FactorM, Divisor, DivisorSum, EulerPhi, Moebius においては，Nが64ビットに収まるならば，ミラーラビン，ポラードローなどを利用します（現状）．
64ビットに収まらない場合は愚直な実装です．
内部で128bit整数 __uint128_t 型を使っています．

xxxList系の関数は特に記述がなければだいたい O(N log N) 時間以内ぐらいのつもり．

  int fac[100], fs[100], fsz;
  int dv[100], dsz;

  fsz = Factor(1500, fac, fs);   // 1500 = 2^2 * 3^1 * 5^3
  rep(i,fsz) wt(fac[i], fs[i]);  // fsz=3, fac={2,3,5}, fs={2,1,3}

  fsz = Factor(1500, fac);
  wt(fac(fsz));                  // 2 3 5

  fsz = FactorM(1500, fac);
  wt(fac(fsz));                  // 2 2 3 5 5 5

  dsz = Divisor(24, dv);
  wt(dv(dsz));                   // 1 2 3 4 6 8 12 24

関数名がよく使う名前なのでこの機能を無効化するフラグがあります（フラグの欄を参照のこと）．
引数の型は違っても構いませんが，計算途中でどのような型になるかは不明です（オーバーフローなどに注意）．
今のところ，整数と浮動小数点数ぐらいでしか上手く動かないと思います．例外的にsum()はstring型でも動くはずです（文字列を連結します）．
配列は長さ0の配列を与えると上手く動かないことがあります．

int i = 10, j = 75;
int k[3] = {100, 200, 300};
wt(gcd(i,j,k(3))); // gcd(10,75,100,200,300) = 5
wt(min(i,j,k(3))); // min(10,75,100,200,300) = 10
wt(sum(i,j,k(3))); // sum(10,75,100,200,300) = 685

min(), max() については（ //no-min() などのフラグを使わなければ）標準のC++の min(), max() を上書きして使えなくなる（両立できなくなる）ので，
std::min(), std::max() と std:: をつけると cLay の機能でなく，C++ のmin(), max() を使います．

int x = -10;
ull y = 4;
ll z;

z = min(x,y) * 1000000000;
wt(z);                 // -10000000000 (min(x,y) はll型の-10になる; 一番桁数が大きいものの符号付きになる)

z = std::min(x,y);     // C++のminでは型が揃ってないのでコンパイルエラー

z = min({1,2,3});      // cLay の機能ではコンパイルエラー
z = std::min({1,2,3}); // C++のminでは z=1 になる

Comb 構造体は（1つ下のconbination_mintのように）階乗などを前計算しておき組合せ的な数を求める構造体です．
Comb<T> comb; で定義したとします．T は mint, modint, Mint, Modint のどれかを想定しています．
必要な値がない場合は，必要になったときに勝手に計算します．

使いそうなの

使わなさそうなの：変数

使わなさそうなの：関数

combination_mint は階乗とその逆数を前計算することで二項係数を高速に求めます．mint型で答えを返します．
構造体を使用しているので combination_mint comb; と最初に宣言して下さい．

  combination_mint comb;
  mint res;

  comb.init(101);     // 100の階乗までを計算．以降 C(100,hoge) まで計算可能
  res = comb.C(5,2);
  wt(res);            // 10 = 5*4/2 = 5個から2個を選ぶ選び方

  int a = 32, b = 24;
  reduceFraction(a,b);
  wtF("{a}/{b}\n");         // 4/3 と表示

  int i, f[10];
  rep(i,10) f[i] = fib_mod(i);
  wt(f(10));                    // 0 1 1 2 3 5 8 13 21 34

double **a, *b, *x;
walloc2d(&a, 3, 2);
walloc1d(&b, 3);
walloc1d(&x, 2);

writerDigit_double(4);

a[0][0] = 3; a[0][1] = 4; b[0] = 5.5;
a[1][0] = 3; a[1][1] = 4; b[1] = 5.5;
a[2][0] = 1; a[2][1] = 2; b[2] = 2.5;

wt(LinearEquation(3, 2, a, b, x));
wt(x(2));

は

0
0.5000 1.0000

と

double **a, *b, *x;
walloc2d(&a, 3, 2);
walloc1d(&b, 3);
walloc1d(&x, 2);

a[0][0] = 3; a[0][1] = 4; b[0] = 5.5;
a[1][0] = 3; a[1][1] = 4; b[1] = 5.6;
a[2][0] = 1; a[2][1] = 2; b[2] = 2.5;

wt(LinearEquation(3, 2, a, b, x));

は

-1

と

double **a, *b, *x;
walloc2d(&a, 3, 2);
walloc1d(&b, 3);
walloc1d(&x, 2);

writerDigit_double(4);
LinearEquation_EPS = 0.5;

a[0][0] = 3; a[0][1] = 4; b[0] = 5.5;
a[1][0] = 3; a[1][1] = 4; b[1] = 5.6;
a[2][0] = 1; a[2][1] = 2; b[2] = 2.5;

wt(LinearEquation(3, 2, a, b, x));
wt(x(2));

は

0
0.5000 1.0000

と出力されます（最後の例は，実装に依存する部分があり，将来的に多少変わる可能性もあります）．

{
  int N = 10;
  int A[10] = {4,1,3,5,3,1,4,3,4,1};
  int len, res[10];
  len = LIS_ends(N, A, res);
  wt(len, ":", res(N));             // 3 : 1 1 2 3 2 1 3 2 3 1
  len = weaklyLIS_ends(N, A, res);
  wt(len, ":", res(N));             // 5 : 1 1 2 3 3 2 4 4 5 3
}

  int n;
  int C[5] = {1000, 100, 1, 8, 100};
  
  n = coordcomp(4, C);
  wt(n);       // 4
  wt(C(5));    // 3 2 0 1 2
  
  int A[5] = {100, 4, 8, 4, 100};
  int B[4] = {8, 2, 1200, 8};
  int rA[5], rB[4];

  n = coordcomp(5, A, 4, B, rA, rB);
  wt(n);       // 5
  wt(A(5));    // 100 4 8 4 100
  wt(B(4));    // 8 2 1200 8
  wt(rA(5));   // 3 1 2 1 3
  wt(rB(4));   // 2 0 4 2

次元圧縮．多次元のグリッドでのBFSなどに．
構造体で，[x]次元のものは dimcomp[x] c; で定義したとする．2次元～5次元まで．

2次元 dimcomp2 c; で定義．

3次元 dimcomp3 c; で定義．

4次元 dimcomp4 c; で定義．

5次元 dimcomp5 c; で定義．

  int dx, dy, mask;
  dimcomp2 c(20,15);    // size = 20 x 15 (dimcomp2 c(15) でもほぼ同じ)
  dx = 3; dy = 9;
  mask = c(dx,dy);
  wt(mask);             // 3 * 15 + 9 = 54
  mask = c(dx+1, dy);
  wt(mask);             // 4 * 15 + 9 = 69
  c(mask,dx,dy);
  wt(dx,dy);            // dx = 4, dy = 9

  {
    int N = 7;
    int A[7] = {7,4,1,4,1,4,1};
    Unique(N,A);
    // N = 3, A = {1, 4, 7}
  }
  {
    int N = 7;
    int A[7] = {7,4,1,4,1,4,1};
    int B[7] = {1,2,2,2,2,2,2};
    Unique(N,A,B);
    // N = 3
    // A = {1, 4, 7}
    // B = {6, 6, 1}
  }

twoMultisets構造体．
格納するデータの型をTとして twoMultisets<T> s; で定義します．格納している要素数を N と書くことにします．
中身は2つのmultisetからなっていて，小さい方のいくつかと大きい方のいくつかを格納しています．
K番目の値を知りたい場合は，小さい方K個と大きい方N-K個を格納するようにする，などと適当に要素を移動させてクエリに答えます．
Kが固定，Kが常にN/2，Kが単調に動く，などの場合に効率的にクエリに答えることができると予想されます．
和を求めることもできますが，和も T 型で格納できる必要があります．
名前の由来は twopointers っぽい動き方しているような気がしたから．

使わないもの

HashMap構造体．
内部ハッシュ（開番地法）でC++のunordered_map的なものを作ります（高速かつ簡単に性能が劣化するケースが作れないようにしたいと思っていますがそうなってるかは謎）．
HashMap<KEY,VAL> hs; で定義したとすると，KEY型の key を使って VAL型の変数 hs[key] を使用できます．
現在 KEY は int, unsigned, ll, ull, pair<int,int> のみに対応．
hs[key] と書いた瞬間（書き込まなくても）hs[key]の要素が作られ，全体を初期化しない限り消せません．逆に一度作ってしまえば以降はずっと同じアドレスを指します（要素数が増えてもリハッシュしたりもしません）．
hs[key] の要素の初期値は不定です．

使わないもの

参考：yukicoder No.1293 2種類の道路
参考：Codeforces Round #684 DIV1 B問題 - Graph Subset Problem

  {
    int d[10] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 4};
    int inv;
    inv = inversion_range(10, d, 1, 9);
    wt(inv); // 14
  }
  {
    double d[10] = {1e3, 1e1, 1e4, 1e1, 1e5, 1e9, 1e2, 1e6, 1e5, 1e4};
    int inv;
    inv = inversion(10, d);
    wt(inv); // 14
  }

非負整数 x, y を2進数で書いたとき，xの1の桁がyの1の桁に包含されているとき，xはyに含まれると呼ぶことにする．
ZetaTransform は res[i] は jがiに包含されている整数を動くとき A[j] の和が代入されます．
メビウス変換はゼータ変換の逆変換です．

  int A[6] = {2,5,9,4,1,8}, B[6], C[6];
  ZetaTransform(6, A, B);
  MoebiusTransform(6, B, C);
  rep(i,6) printf("%d %d%d%d %02d %02d %02d\n", i, (i>>2)%2, (i>>1)%2, i%2, A[i], B[i], C[i]);
// 0 000 02 02 02
// 1 001 05 07 05
// 2 010 09 11 09
// 3 011 04 20 04
// 4 100 01 03 01
// 5 101 08 16 08

res[i] は jがiに包含されている整数を動くとき A[j] の最小値 | 最大値を求めるのは以下の関数です．
小さい方から2個，3個求めるものもあります．この場合は，要素数が足りない場合は，numeric_limits<S>::max();が代入されます．

また，逆に，res[i] に i を包含する j についての A[j] の和
$\displaystyle res[i] = \sum_{j \in i} A[j]$
を求める高速ゼータ変換，その逆変換のメビウス変換は以下の通り．

  int N = 10;
  int A[10] = {0,0,1,1,1,0,0,3,2,1};  // 0が2個 - 1が3個 - 0が2個 - 3が1個 - 2が1個 - 1が1個
  int e, val[10], len[10];

  e = runLength(N,A,val,len);
  wt(e);                         // 6 と表示されます
  wt(val(e));                    // 0 1 0 3 2 1
  wt(len(e));                    // 2 3 2 1 1 1

いずれの関数も，空のmultiset, setを引数に取ってはいけません．

基本的にグレゴリオ暦を仮定

  int A[10] = {1,2,3,1,2,3,1,2,3,1};
  int B[4] = {1,2,3,1};
  int res[10], cnt;

  cnt = KMP(A, 10, B, 4, res);
  wt(cnt);      // 3
  wt(res(10));  // 1 0 0 1 0 0 1 0 0 0

  char S[12] = "abracadabra";
  int SA[12], LCP[12];
  SuffixArray(S, 11, 128, SA, LCP);
  rep(i,12) printf("%4d %4d %4d %s\n", i, SA[i], LCP[i], S+SA[i]);
  /*
   0   11   -1
   1   10    0 a
   2    7    1 abra
   3    0    4 abracadabra
   4    3    1 acadabra
   5    5    1 adabra
   6    8    0 bra
   7    1    3 bracadabra
   8    4    0 cadabra
   9    6    0 dabra
  10    9    0 ra
  11    2    2 racadabra
  */

Arr1d 構造体．
累積和を計算しておけば連続する部分列の和を計算できたりするような，1回準備したら（配列の中身を変更しなければ）簡単に答えられるようなクエリに対応するための型です．
（計算状況リセットしてから）最初の1回のみ，連続部分列の和を取得しようとしたときに累積和を計算するような感じ．
以下は，Arr1d<T> a;を想定．

[特殊な話]
int n; Arr1d<ll> a;
rd(n, a(n));
と読み込むことができます．
rd(a(n));で読み込んだときには，読み込む直前に a.malloc(n); が走って勝手にメモリ確保と配列サイズが指定されます．
a[0], a[1], ..., a[n-1] で普通に要素にアクセスできます．

[コンストラクタ・メモリ関係・初期化など]

[累積和関係]

[縦横に連続する数]

[ヒストグラム（密な場合）]

[ヒストグラム（疎な場合）]

[左右の次の大小関係の要素を探す]

[その他]

[基本的に使わない情報]

Arr2d 構造体．
以下は，Arr2d<T> a; を想定．

[特殊な話]

int n1, n2; Arr2d<ll> a;
rd(n1, n2, a(n1,n2));

と読み込むことができます．
rd(a(n1,n2)); で読み込んだときには，読み込む直前に a.malloc(n1,n2); が走って勝手にメモリ確保と配列サイズが指定されます．
a[0][0], ..., a[n1-1][n2-1] で普通に要素にアクセスできます．

[コンストラクタ・メモリ関係・初期化など]

[累積和]

[斜め累積和]

[縦横に連続する数]

[基本的に使わない情報]

Grid1d構造体．
Grid1d<int> g; などで定義し，g.malloc(n); でメモリを確保する．メモリ解放するときは g.free(); ．
すると，g[i]が使えるようになり，それぞれint型．
g[i] にデータを代入して，g.setSum()，g.setDir() 等で累積和などのテーブルを作成して，利用する．
データを変更した場合は，g.setSum() などを再度呼び出せば良い．
行の数，列の数を変更する場合は，現状，g.free()→g.malloc(n)とやり直すしかない．
以下は，Grid1d<T> g;を想定．

累積和関係

縦横に連続する数

Grid2d構造体．
Grid2d<int> g; などで定義し，g.malloc(r,c); でメモリを確保する．メモリ解放するときは g.free(); ．
すると，g[i][j]が使えるようになり，それぞれint型．
g[i][j] にデータを代入して，g.setSum()，g.setDir() 等で累積和などのテーブルを作成して，利用する．
データを変更した場合は，g.setSum() などを再度呼び出せば良い．
行の数，列の数を変更する場合は，現状，g.free()→g.malloc(r,c)とやり直すしかない．
以下は，Grid2d<T> g;を想定．

累積和関係

縦横に連続する数

その他

FFTを用いて畳み込みを行います．
誤差がそれなりにのるので使用する際には注意．

FFTを用いて畳み込みを行います．
mod の値は 2冪+1 でなければならないなどの条件が存在します．
root には mod の原始根のうちの1つを指定してください．defineしたMDが素数の場合，その原始根は MD_PRIMITIVE_ROOT で勝手にdefineされます．

  double a[3] = {1,2,3}, b[3] = {1,2,3}, c[6];
  convolution(a, 3, b, 3, c, 6);
  wt(c(6));  // 0.999999999999999 3.999999999999999 10.000000000000000 12.000000000000000 9.000000000000000 0.000000000000001
  convolution(a, 3, c, 6);
  wt(c(6));  // 0.999999999999999 3.999999999999999 10.000000000000000 12.000000000000000 9.000000000000000 0.000000000000001

FFT単体を行う関数は以下の通りです（上手く使いまわしてFFTの回数を減らす場合はこちら）．配列の長さは2の冪でなければいけません．
fft_pnt構造体は struct fft_pnt{ double x, y; } で x + yi という複素数を表すもので +-* の3種の演算子が定義されています．
FFT，逆変換ともに定数倍を考慮していません．配列の長さ nでFFTして畳み込みを計算する場合は，FFTして，要素ごとに掛け算して，逆変換した後，各要素を 1/n 倍する必要があります．

参考：TOKI Regular Open Contest #17 H問目 - Guitar Gift

高速Walsh-Hadamrd変換を用いたxor convomution（xor畳み込み）．
$\displaystyle R[k] = \sum_{k = i \oplus j} A[i] B[j]$
となる配列を求めます（$\oplus$ はbitwise xor）．
配列の型は現在 Modint, modint, Mint, mint, double ぐらいのみを想定．

高速Walsh-Hadamrd変換自体は以下の通り．
配列のサイズは2の冪である必要があります．xor畳み込みをする場合，自力で最後に各要素を配列サイズnで割る必要があります．
配列は上書きします．

高速ゼータ変換を用いたand convolution（and畳み込み）とor convolution（or畳み込み）．
$\displaystyle R[k] = \sum_{k = i\ \mathrm{and}\ j} A[i] B[j]$
$\displaystyle R[k] = \sum_{k = i\ \mathrm{or}\ j} A[i] B[j]$
となる配列を求めます．
配列の型は現在 Modint, modint, Mint, mint, double ぐらいのみを想定．

and convolutionの方は，ZetaTransform2()を行い，要素ごとにかけた後，MoebiusTransform2()を行えば得られますが，要素数が2の冪でないときに注意．
or convolutionの方は，ZetaTransform()を行い，要素ごとにかけた後，MoebiusTransform()を行えば得られますが，要素数が2の冪でないときに注意．

グラフの隣接リスト（隣接配列？）のようなものを作ります．
時間ごとにイベントを処理する場合などの整理などにも多分便利．

    int A[5] = {1,1,3,3,0}, B[5] = {10,30,30,30,50};
    int *es, **edge;
    wAdjEdge(4, 5, A, B, &es, &edge);
    rep(i,4) wt(i, ':', es[i], ':', edge[i](es[i]));
//  0 : 1 : 50
//  1 : 2 : 10 30
//  2 : 0 :
//  3 : 2 : 30 30

ハンガリアン法．n ≤ m と仮定．
mat[0][c[0]] + mat[1][c[1]] + ... + mat[n-1][c[n-1]] の最小値を求める．ただし，c[i]は互いに異なる（c[i]は0以上m未満）．
それを達成する配列cはmatch[]に代入して返す．matchにNULLにしておくと最小値だけ返す．

多項式補間（ラグランジュ補間）．
f(x[i]) = y[i] （i=0,1,...,n-1）となる n-1 次以下の多項式 f を考える．

効率的な実装にはなっていない（遅い）です．
Explode("hoge,piyo,,123,", ",") は {"hoge", "piyo", "", "123", ""} を返します．
Explode("hoge,,,piyo,,123,", ",,") は {"hoge", ",piyo", "123,"} を返します．
v = {"hoge", "piyo", "", "123", ""} のとき Implode(v, "-") は "hoge-piyo--123-" を返します．

二次元幾何．まだだいぶ怪しいです（作りかけだと思ったほうが良い）．
Point2d<T,S,F> p; で定義したとします．
Tは座標の型，Sは座標の二乗以上のオーダーになる場合の型，Fは整数計算で収まらない場合の型です．
標準的には，できるだけ整数で計算する場合は Point2d<int,ll,double> p; で，そうじゃない場合は Point2d<double,double,double> p; で．

これ以内の差ならば同じとみなす（場合がある）定数を型ごとに指定できます．
（現状の）標準では，double型，long double型は1e-10，float型は1e-4になっています．
{Point2dEPS<double> tmp; tmp.set(1e-13);} で 1e-13 になります．

rd(), wt() に対応（単にx,yを並べて出力）してると思います．
s = sum(a(n)) は未対応です．s = sum[i,0,n](a[i]); はできます．

コンストラクタ系

オペレータ（メンバ関数）

オペレータ（その他）

メンバ関数

その他関連関数

配列の部分集合の和．
全て O(2^n) 時間ぐらい．ソートする場合は列挙しながらマージソートします．
重複を取り除く場合などで答えが少ないなら O(n*答えの数) 時間ぐらいになります．ただし，その場合はビットセットを利用したDPなどのほうが高速になる場合が多いです．

  int n = 4, a[4] = {3,0,4,3};
  int sz, res[16] = {};

  rep(mask,1<<n) rep(i,n) if(mask&1<<i) res[mask] += a[i];
  wt(res((1<<n)));                  // 0 3 0 3 4 7 4 7 3 6 3 6 7 10 7 10

  sz = subsetSum(n, a, res);
  wt(res(sz));                      // 0 3 0 3 4 7 4 7 3 6 3 6 7 10 7 10
  sz = subsetSumS(n, a, res);
  wt(res(sz));                      // 0 0 3 3 3 3 4 4 6 6 7 7 7 7 10 10
  sz = subsetSumS(n, a, res, 6);
  wt(res(sz));                      // 0 0 3 3 3 3 4 4 6 6
  sz = subsetSumSD(n, a, res);
  wt(res(sz));                      // 0 3 4 6 7 10
  sz = subsetSumSD(n, a, res, 6);
  wt(res(sz));                      // 0 3 4 6

部分和問題（subset sum）を解く系列の関数群（ナップザックも作りたいね）．
入力のサイズなどから使用メモリが mem_lim を超えなさそうで，一番高速っぽいアルゴリズムを選択します．

以下は内部で呼び出すことを想定していますが，アルゴリズムを指定したい場合は直接呼び出して良いです．また，使用するアルゴリズムを選択する部分が重くて駄目な場合なども．

Modint **res, **cnt1, **cnt2;
cntArrayNecessaryElement_walloc(2,3,&res,&cnt1,&cnt2);   // 0, 1, 2 のみからなる長さ2の配列
wt(res[2][1]);   // 5   ({0,0}, {0,1}, {0,2}, {1,0}, {2,0} の5個：0を必ず含むもの)
wt(cnt1[2][1]);  // 6   (↑に出てくる0の個数)
wt(cnt2[2][1]);  // 2   (↑に出てくる1の個数や2の個数)

ローリングハッシュ．
配列 A[0], A[1], ..., A[N-1] をハッシュ関数値 $\sum r^k A[k] \bmod p$ に対応させます．
p は $2^{61}-1$ で固定，r は $3^k$ (gcd(k,p-1) = 1) の中からランダムに選ばれます（配列の値の範囲（幅）が2^61以上とかだと危険です．衝突の危険も少しあります）．
128ビット整数（__uint128_t 型）を使用しますので，32ビット環境などでは動きません．

struct rollingHash {ll len; ull hs;} は配列の長さ len とハッシュ関数値 hs を表す構造体です．
以下 rollingHash h; で定義したとします．

配列から rollingHash を取得するには，以下の関数を利用します．

rollingHash 構造体で使える機能は以下のとおりです．

配列に対して，その連続する部分列の rollingHash を取得するには，rollingHashSubarrays 構造体を利用します．
rollingHashSubarrays はハッシュ値の累積和を記憶しておきます．
以下 rollingHashSubarrays arr; で定義したとします．

r^k を計算する必要があるとき，|k| がある程度より小さい場合は，適当に前計算したものを利用します．
大きい場合（2*10^6ぐらいを超える場合）はバイナリ法で計算します．
配列の長さが 2^63 以上，あるいは，それに近い場合は動かないと思います．

その他の情報など：

参考：Educational Codeforces Round 101 E問題 - A Bit Similar

ほぼ使わないもの（内部的に使っているもの）

更新履歴

これ以前の更新履歴はこちら．