2019年07月21日14時33分21秒に更新されたバージョンを表示しています．
最新のページはこちらをご覧ください．

cLay概要（version 20190721-1）

概要

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

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

コードはこちら（最新版はこちら）．C++っぽいコードを標準入力から食わせるとC++のコードが標準出力から出てきます．

未対応なもの

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

制限

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

chmax, chmin,
ll, ull, mint, segtree, combination_mint,
rd, reader,
wt, wtLn, wtSp, wtN, wtF, wt_L, writer, writerLn, writerSp, writerN, writerF,
min, max, argmin, argmax, argminL, argmaxL,
gcd, GCD, lcm, LCM, sum, SUM, mul, MUL,
sortA,
reduceFraction, runLength,
wmem, memarr,
malloc1d, malloc2d, free1d, free2d, walloc1d, walloc2d,
int_inf, ll_inf, double_inf, MD, PI

色々

最初に

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

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

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

変数宣言の順番は勝手に変わります．
また，変数宣言はブロックの最初に移動します．
変数宣言と同時に初期化する場合に注意して下さい．
変数宣言をした場所で変数を宣言したい場合は，inplace_L 修飾子をつけるとその場所で宣言されます．
（また，初期値にループを使わないと計算できないものを指定すると，宣言はブロックの最初に移動しますが，初期値の代入はその場所で行われることがあります）

{                                {
  int i = 1, j = 2;                  int i = 1, j = 2;
  j++;                               j++;
  int a = i + j;                     inplace_L int a = i + j;
}                                }

は，それぞれ以下のようになります（必要部分だけ抜粋）．

  int a=i + j, i=1, j=2;             int i=1, j=2;
  j++;                               j++;
                                     int a = i + j;

フラグ

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

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

型

llはlong longに，ullはunsigned long longに置き換えられます．

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の詳しい仕様はそのうち書きます．

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

入出力

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]) に置き換わります．グラフのエッジの入力とかに．
rdの代わりにreaderでもOK．
rdは今のところint型，ll型，double型，mint型，char型の配列（文字列）にのみに対応．他の型もそのうち対応．
また，char S[1000]; int N; rd(S@N);で文字列 S を読み込むと同時に文字列の長さを N に代入します．複数の文字列の場合は char S[10][1000]; int N[10]; rd(S@N(10)); とS@Nはひとかたまりで扱います．

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

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型の配列（文字列）のみに対応．他の型もそのうち対応．
wtFは文字列を出力しますが，変数名を{}で囲むと，その変数の値に置換されて出力されます．文字列中で{または}を出力したい場合はエスケープして\{または\}と書きます．

また，出力に関してオプションで 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]);
}

標準入出力ではない場合は，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に書き込み

ループ

rep(i,n)およびREP(i,n)はfor(i=0;i<n;i++)に置き換えられます．
rep(i,a,b)およびREP(i,a,b)はfor(i=a;i<b;i++)に置き換えられます．
また，この際，変数iが宣言されていなかった場合，勝手にint型の変数として宣言されます．

また，括弧内（(),[],{}のどれか）で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個以上ドットが並ぶとバグる実装なのでそのうちなんとかする．

演算子

昔のGCC拡張で存在した<?および>?演算子の同時に代入するバージョンのみ使えます．
つまり，a <?= b; は a = min(a, b); と，a >?= b; は a = max(a, b); と大体同じです．
代入しないバージョンは素直にminおよびmaxを使え．

正の整数に関する繰り上げの割り算演算子 /+ が使えます．
13 /+ 3 は 5 となります．
実際には a /+ b は (a+b-1) / b で定義され，正の整数でないと繰り上げ割り算になる保証はありません．
また，a+b-1 がオーバーフローする可能性があるので要注意です．

負の数を正の数で割った余りを非負の数で返す %% 演算子があります．
(-5) %% 2 は 1 になります．
演算子の優先順位が低いので，-5 %% 2 は-(5 %% 2) = -1になります．

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

数値の後の掛け算の演算子*は省略できることがあります．
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 > の場合は，テンプレート絡みなどで使用することがあるので，この場合のみ展開されません．

定数

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$ 以下でないと正しく動きません．

ワーキングメモリ

ワーキングメモリを必要な関数や機能などを使うと勝手にワーキングメモリを確保します．
void *wmem; に（デフォルトで）96,000,000バイトのメモリが確保されます．

行列

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

コンストラクタ

その他

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); とします．

使える感じの関数は以下の通り（要素数を $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
  }

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

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

よく使いそうなもの：

そうではないもの：

  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();とすれば使えるようになります．

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

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

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

グラフ（構造体）

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

{
  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; などで定義します．

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; を定義します．
ノードに値を持ちます．
（枝に値をもたせたい場合は，すぐ上に向かう枝の値をノードに持たせて，LCAでパスを分割したりするとできるかも）

以下 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; とします．
徐々に流していくアルゴリズムを適当に実装したもので，少なくても現状は良い実装ではないと思います．
負の閉路などがあると動きません．

AhoCorasick

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

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

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

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

その他色々な関数など

  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)を使って設定．

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

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

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

以下あまり使わないやつ

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

  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)

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

  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 と表示

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

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

  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);

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

facは異なる素因数，fsはその素因数を何個持つか．

  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

関数名がよく使う名前なのでこの機能を無効化するフラグがあります（フラグの欄を参照のこと）．
引数の型は違っても構いませんが，計算途中でどのような型になるかは不明です（オーバーフローなどに注意）．
今のところ，整数と浮動小数点数ぐらいでしか上手く動かないと思います．
配列は長さ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

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

  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

  {
    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}
  }

  {
    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
  }

  int i, 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

  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を引数に取ってはいけません．

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

更新履歴

Current time: 2023年05月30日09時11分15秒
Last modified: 2019年07月21日14時33分21秒 (by laycrs)
Tags: no_tags
トップページに戻る

Logged in as: unknown user (not login)

ログイン：