Senの競技プログラミング備忘録

こけた問題を自分用の解説で載せる。けんちょんさんのブログを目指したい。質的にも量的にも。こけた問題だけに限定するけど

ACL Beginner Contest F - Heights and Pairs

https://atcoder.jp/contests/abl/tasks/abl_f

問題概要

$ 2N $人の人がいて、それぞれ身長が$ h[i] $である。 この人たちで、ペアを$ N $組作っていく。(任意の人は1つのペアにしか属してはいけない)

ここで、すべてのペアのうちの2人で、お互いの身長が異なるという前提で作ることにする。

この時、何通りのペアの組方があるのでしょう?$ 998244353 $で割ったあまりを答えてください。

ただし、別にカウントする条件は、すでにあるどの組方とでも、少なくとも1ペア以上で構成員が異なるである。

入力:$ 1 \leq N \leq 50000, 1 \leq h[i] \leq 100000 $

続きを読む

ARC059 - キャンディーとN人の子供

https://atcoder.jp/contests/arc059/tasks/arc059_c

問題概要

N人の子どもがいる。それぞれ、はしゃぎ度という整数値A[i]があるとする。 この時、それぞれの子どもが飴をB[i]個もらっているとき、全体の活発度は以下のように求められる。 $$ \Pi _ {i = 1} ^ {N} A[i] ^ {B[i]} = A[1] ^ {B[1]} \cdot A[2] ^ {B[2]} \cdot ... $$

始めに飴をC個持っているとする。この飴の全通りの配り方をしたときに、対応する{A[i]}の組での活発度の和を$ f(A[1], A[2], \cdots, A[N]) $とする。

Subtask1

{A[i]}が与えられる。この時のfをmod $ 10 ^ 9+7 $で求めよ。

制約: $ 1 \leq N \leq 400, 1 \leq C \leq 400, 1 \leq A[i] \leq 400 $

Perfect Task

{A[i]}が与えられる代わりに、{A[i]}と{B[i]}が与えられる。以下の式をmod$ 10 ^ 9 + 7 $求める。 $$ \sum _ {x _ 1 = A[1]} ^ {B[1]} \sum _ {x _ 1 = A[2]]} ^ {B[2]} \cdots f(x _ 1, x _ 2, \cdots, x _ n) $$

制約: $ 1 \leq N \leq 400, 1 \leq C \leq 400, 1 \leq A[i] \leq B[i] \leq 400 $

続きを読む

NTT(数論変換)のやさしい解説

この記事は、高速フーリエ変換の1つのバリエーションである、Numeric Theory Translation(数論変換)の詳しい解説記事です。 あまりなかったので書きました。 数論変換にありがちな

  • なんで$ 10 ^ 9 + 7 $じゃダメなのか
  • 原始根って何?

とかについてもこれを見ればわかります。

前提知識としては、Fast Fourier Translation(高速フーリエ変換)が必要です。 kaage大先生のQiita記事とかは中高生にもわかりやすく書かれています。

下に一応自分の勉強ノートを載せます。(上の記事の行間を埋めた感じです)

では、数論変換について説明したいと思います。

高速フーリエ変換の弱点

高速フーリエ変換は正しいですが、弱点として精度が足りないというのがあります。 なぜならば、複素数の1の$ 2 ^ m $乗根は計算上ではれっきとした64bit倍精度浮動小数点のdoubleのペアなので、$ m $が増えるとdoubleではどうしても精度が足らなくなります。

一例として、$ (10x ^ 9 + 9x ^ 8 + 8x ^ 7 + 7x ^ 6 + 6x ^ 5 + 5x ^ 4 + 4x ^ 3 + 3x ^ 2 + 2x + 1) ^ 2 $の畳み込みを見てみましょう。自作のFFTの計算結果は以下です。

(1, 7.43086e-14)
(4, 1.03461e-13)
(10, 1.03814e-13)
(20, 1.16975e-13)
(35, 1.51601e-13)
(56, 1.64745e-13)
(84, 1.56105e-13)
(120, 1.48062e-13)
(165, 1.53148e-13)
(220, 1.27886e-13)
(264, 8.78265e-14)
(296, 2.90458e-14)
(315, -6.56697e-14)
(320, -1.01708e-13)
(310, -1.21006e-13)
(284, -1.0951e-13)
(241, -1.74825e-13)
(180, -1.87862e-13)
(100, -1.75074e-13)

実数部分は問題ありませんが、複素部分は$ 10 ^ {-13} $オーダーのエラーが出ています。倍精度浮動小数点の計算機イプシロン(double型で表す1より大きい最小の数)が$ 2.220 \times 10 ^ {-16} $ であることを考えると、なかなかに無視できない誤差ではないかとわかります。

実際、畳み込みの結果が$ 10 ^ {8} $オーダーになると、倍精度浮動小数点では精度が足りなくなります。そして、畳み込みなどを使う数え上げではこの限界をいとも簡単に突破する問題が多いです。

FFTアルゴリズム自体は正しいのですが、計算機の精度保持の限界の問題で大きな値は正しく計算できないのです。

FFTのn乗根

FFTのn乗根は、複素数$ \zeta _ n = (\cos \frac{2 \pi}{n} + i \sin \frac{2 \pi}{n}) $が採用されていました。この値は、以下の性質を持っていました。

  • $ \zeta _ n ^ 0, \zeta _ n ^ 1, \cdots , \zeta _ n ^ {n - 1} $の値はみんな違う。
  • $ \zeta _ n ^ n = 1 $(n乗すると単位ユニット(=単位元)になる)
  • $ \sum _ {i = 0} ^ {n - 1} (\zeta _ n ^ k) ^ i $は$ 0(k \neq 0) $か$ n(k = 0) $

逆に言うとこれを満たすものであれば、離散フーリエ変換に代入する値としてOKです。(FFTをするために$ n = 2 ^ m $の形としないといけないけど)

複素数の世界では、候補はこれしかありませんでした。しかし、世界を変えてみるとどうなるでしょう?

mod pの世界

整数を$ p $で割ったあまりの世界(剰余環)を考えます。この世界での四則演算について考えると、割り算以外なんでもできそうな気がします。 そして、$ p $が素数の場合、割り算も定義できます。(けんちょん大先生の記事を参考)

そして、この世界で、$ n $乗したら1になるものも$ n $乗根といいます。

mod pの世界の原始根

ここで、mod $ p $($ p $は素数)の世界の原始根という考え方を説明します。

mod $ p $の世界で、ある要素$ g $があって、$ g ^ 0, g ^ 1, g ^ 2, \cdots , g ^ {p - 2} $がみんな違う値を取るような$ g $を原始根といいます。

詳しいのはけんちょんさんと同じ研究室の人が書いた高校数学の美しい物語の記事をご覧ください。

mod pの世界での離散フーリエ変換

mod $ p $(素数)の世界でも、$ n=2 ^ m $乗根にあたるものを考えてみます。これは$ g ^ n = 1 $を満たす必要があります。ところで、mod $ p $の世界で有名なフェルマーの小定理があり、 $$ g ^ {p - 1} \equiv 1 (mod p) $$

が成り立ちます。このことから、$ p = 2 ^ m \times a + 1 $($ a $は2と互いに素)と書ける場合、 $$ g ^ {2 ^ m \times a} \equiv 1 (mod p), (g ^ {a}) ^ {2 ^ m} \equiv 1 (mod p) $$

となります。つまり、 $ 2 ^ m $乗根は$ g ^ {a} $ となります。(一方で、$ 2 ^ {n + 1} $乗根は存在しません)

これで、複素数の上で定義していた$ 2 ^ m $乗根を定めることができました。 これを2乗することで、$ 2 ^ {m - 1} $乗根も複素と同様に定めることができますので、mod $ p $の上の1乗根、2乗根、4乗根、...、$ 2 ^ {m} $乗根と全て求められます。

mod $ p $の上での割り算も定義されているので、FFTをmod $ p $の世界で考えることができました。

$ 10 ^ 9+7 $と$ 998244353 $の違い

NTT有名素数modとして、$ 998244353 $が挙げられます。この値は、 $$ 998244353 = 2 ^ {23} \times 119 + 1 $$ となります。

これは、mod $ 998244353 $では$ 2 ^ {23} $乗根まで存在する($ 2 ^ {24} $乗根はない)ということです。 $ 2 ^ {23} $乗根まで存在するので、mod $ 998244353 $の世界で$ 2 ^ {23} = 8300608 $から、$ 8388607 $次までの畳み込みを、FTTと同じように分割統治で計算することができます。

このことから、競プロでは一般的に実用的な畳み込みの余りは$ 998244353 $となっています。

一方、$ 10 ^ 9 + 7 $の場合 $$ 10 ^ 9 + 7 = 2 ^ 1 \times 50000003 + 1 $$ であります。

これは、mod $ 10 ^ 9 + 7 $ の世界では、2乗根までしかなく、4乗根すらないということです。 つまり1次式までしか畳み込みできません。 さすがにこれは使えないです。

$ 10 ^ 9+7 $で無理やり畳み込みをするには?

mod $ 10 ^ 9+7 $は1の4乗根が存在しないことから、畳み込みはかなり困難になります。一応頑張ればできるらしいのですが、計算量的にも実装量的にも手法的にも全く実用的ではありません。しかし、任意modでの畳み込みをしたいというのならば、複数回のNTTとGarnerのアルゴリズムというもので復元できます。

やり方の詳細はここにあります。

実装例

確認問題

//mintはModintである。
//畳み込みをする前にsetup()を実行する。
typedef std::vector<mint> vectorM;//NTT用のmintのベクター型
const int DIVIDE_LIMIT = 23;//99...の有名素数は23回分割統治できる。
mint ROOT[DIVIDE_LIMIT + 1];//[i]は2^i乗根 99...の有名素数の原始根は3で、そこから2^22乗根, 2^21...などをsetup()で計算する。
mint inv_ROOT[DIVIDE_LIMIT + 1];//[i]は2^i乗根の逆数 setup()で計算する。
mint PRIMITIVE_ROOT = 3;

void setup() {
    ROOT[DIVIDE_LIMIT] = modpow(PRIMITIVE_ROOT, (MOD - 1) / modpow(2, 23).val);//99..なら119乗
    inv_ROOT[DIVIDE_LIMIT] = 1 / ROOT[DIVIDE_LIMIT];
    for (int i = DIVIDE_LIMIT - 1; i >= 0; i--) {
        ROOT[i] = ROOT[i + 1] * ROOT[i + 1];
        inv_ROOT[i] = inv_ROOT[i + 1] * inv_ROOT[i + 1];
    }
}

vectorM ntt(const vectorM& f, const int inverse, const int log2_f, const int divide_cnt = DIVIDE_LIMIT) {
    vectorM ret;
    if (f.size() == 1 || divide_cnt == 0) {
        ret.resize(f.size());
        mint zeta = 1;
        for (int i = 0; i < ret.size(); i++) {
            mint now = zeta;
            for (int j = 0; j < f.size(); j++) {
                ret[i] += f[j] * now;
                now *= zeta;
            }
            zeta *= ((inverse == 1) ? ROOT[0] : inv_ROOT[0]);
        }
        return ret;
    }

    vectorM f1(f.size() / 2), f2(f.size() / 2);
    //f1とf2を作る。
    for (int i = 0; i < f.size() / 2; i++) {
        f1[i] = f[i * 2];
        f2[i] = f[i * 2 + 1];
    }

    vectorM f1_dft = ntt(f1, inverse, log2_f - 1, divide_cnt  -1), f2_dft = ntt(f2, inverse, log2_f - 1, divide_cnt - 1);
    ret.resize(f.size());
    mint now = 1;

    for (int i = 0; i < f.size(); i++) {
        ret[i] = f1_dft[i % f1_dft.size()] + now * f2_dft[i % f2_dft.size()];
        now *= ((inverse == 1) ? ROOT[log2_f] : inv_ROOT[log2_f]);
    }
    return ret;
}

//eraseHigh0は高次項が係数ゼロ、vectorから排除するかどうか
vectorM mulp(const vectorM& _f, const vectorM& _g) {
    vectorM f = _f, g = _g;

    //fとgの次数の和以上の最小の2冪-1を次数とする。
    int max_dim = 1, log2_max_dim = 0;
    while (f.size() + g.size() > max_dim) max_dim <<= 1, log2_max_dim++;
    f.resize(max_dim), g.resize(max_dim);
    //多項式fとgのDFT結果を求める。 O(n log n)
    vectorM f_dft = ntt(f, 1, log2_max_dim), g_dft = ntt(g, 1, log2_max_dim);

    //f*gのDFT結果は各f_dftとg_ftの係数の積。O(n)
    vectorM fg_dft(max_dim);
    for (int i = 0; i < max_dim; i++) {
        fg_dft[i] = f_dft[i] * g_dft[i];
    }

    //fg_dftをDFT
    vectorM fg = ntt(fg_dft, -1, log2_max_dim);

    //最後にmax_dimで割る
    for (int i = 0; i < fg.size(); i++) {
        fg[i] = fg[i] / max_dim;
    }
    return fg;
}

最後に

NTTについてかなり一杯学べました。これがみんなの役に立てれば幸いです。

参考文献

AGC045 - A - Xor Battle

atcoder.jp

概要

以下の問題がTケース与えられるので、それについてT回回答すること。

長さNの配列{A_i}が与えられる。そして、もう1つ長さNの文字列Sが与えられ、それは0と1のみに構成される。0さんと1さんの2人はこの数列を使って、次のようなルールでゲームを行う。

  •  xという変数を用意し、 x=0で初期化する。
  • S[i]が0だったら0さんの手番、1だったら1さんの手番
  • 自分の手番では、 x \leftarrow x \otimes A_iを行うか、何もしない。

各々最善を尽くした時に誰が勝者になるのでしょう?

制約:
1 <= T <= 100, 1 <= N <= 200, 1 <= A[i] <= 10^18, |S| = Nで0か1で構成されている。

解法

以下は全部1-indexで解説する。

このようなゲーム問題では、詰んだ局面から逆算するのが常であるので、詰む=勝ち確定の局面をいくつか考察していく。

S="*1"(最後が1のような文字列)の場合

この場合は、明らかに1さんが勝つ。なぜならば、最後の手番が回ってきたとき

  •  x = 0ならXORをする。この時 A_i \neq 0より必ず x \neq 0
  •  x = 0ならXORをしない。何もしなくても勝てるからである。

S="*10"(最後が10のような文字列の場合)

この場合は、1さんがN-1手目で x=0 x=A_{i-1}を作ってしまった or 作らざるを得なかった場合、0さんはXORをしない or することで必ず x=0にすることができる。
逆に、1さんがN-1手目で x\neq0, x\neq A_{i-1}を満たせれば1さんの勝ちが確定するのだ。

しかし、これだけではまだ難しい。なぜならばN-1手目にたどり着くまでには1さん以外にも0さんの手番が存在しているので、1さんが一意に xの値を決められるとは限らないので、考えるのが難しいと思えるからだ。

では、逆に今 i手目を見ているとして、 1からi-1手目に関係がなくいくつかの局面での勝ち負けを断定する方法はあるのだろうか。これについて掘り下げると、どうやら A_iの値が重要らしい(情報量0の発言)。

ここで、 i=N-1の時、 A_{N-1}=A_Nの時を考える。この時、最後の2手についてだけ言うのであれば、お互いに打ち消せる手であると認識できる。(XORは2回すると元に戻る。1さんがやる->0さんがやる or 1さんがやらない->0さんがやらない)

逆に、 A_{N-1}\neq A_Nの場合ではどうだろうか。実はこの時は1さんの勝利が確定するのである。 A_{N-1} A_Nでは打ち消せないことを解釈すると以下のようになる。

  •  A_{N-1}にはどこかの桁などで A_Nと違っていて、その結果お互いに打ち消すことが不可能。その違う桁の位の集合をXとする。
  •  N-1手までに、Xに入っている桁の位たちが、 xですべて立っていなかったら、1さんは A_{N-1}をXORすることで立てることができる。
  •  N-1手までに、Xに入っている桁の位たちが、 xで1つでも立っていたら、1さんは手番をパスすれば、0さんは必ず N手目でそれを消すことができない。

よって、 A_{N-1}\neq A_NかつS=(0+1)^*10の場合、1さんが勝利確定である。

逆に、 A_{N-1}=A_Nの時は、まだ勝負はわからない。これは最後の2手を削って再び考えることができる。

S="*100"、(最後が...100で終わる)の場合

この場合に先ほどの考えを適用させて考えてみる。この時、先ほどの A_{N-1}=A_Nであるか?という条件は、少し考えると、 A_{N-1} A_Nを自由にXORして、 A_{N-2}を作れるか?」というのにかわるとわかる。

つまり、 A_{N-1} A_Nをそれぞれ1回までXORに使用可能なときに、 A_{N-2}を作れるか?という問題に対して、

  • 作れる=まだ勝負はわからないとして、もう1つ前を見ていく。
  • 作れない= A_{N-2}を1さんがXORすれば勝ち確定。

と先ほどのS="*10"から拡張できる。

これをさらに拡張すると、以下のような事実が得られる。

 S=(0+1)^*10^+について、1が i手目だとして、 A_i A_{i+1}からA_{N}まで各々最大1回まで使ってXORして、

  • 作れる=勝敗決定できないので、 i-1手目を見ることになる。( i-1手目が0さんの手番なら、これより前の1さんの動作に対して使えるかもしれない切り札が1つ増えるだけである)
  • 作れない=1さんがこれをXORすればいいので、1さんの勝ちである。

これで勝敗決定問題をかなり一般化できた。

ところで、理系大学生などの方は、これが線形代数線形空間、基底という概念とこれは非常に似ていることに気づかないだろうか?

実は、XORという演算は各桁に分解すると、「mod 2の上で行われている演算」であると言い換えることができ、今回の場合 A_i \leq 10^{18} \approx 2^{60}であることから、 A_i xのXORは、60次元のmod 2上でのフィールドそのものであるとみなせる。

そして、いくつかのベクトルを好きな個数だけ、自由に足し引き出来るとき、指定したベクトルが作れるか?は明らかに線形空間に含まれるベクトル、ひいては基底で求められるベクトルが作れるか?と全く同じことである。

というわけで、後は線形代数の問題を解決できれば、この問題は解けたと言えるだろう。

線形空間と基底については以下の解説サイトなどで参考してください。

線形空間(ベクトル空間)を画像と具体例で解説 | 大学1年生もバッチリ分かる線形代数入門

【線形空間編】基底と次元と成分 | 大学1年生もバッチリ分かる線形代数入門

つまり、
 \vec{x} \in S \vec{x}を毎回たかだか1本まで足すことができるmod 2の60次元の線形空間で、 \vec{y}を作れるか?という問題と全く同じである。

まず、 \vec{x} \in Sを基底にまとめ直そう。( x_3=x_2 \otimes x_1 | x_1,x_2,x_3 \in Sがあるのならば、 x_3は不要。)これは、すべての基底候補のベクトルを縦or横に並べた行列を作って、行列の基本変換を施すことで変形できる。

ちなみに、行列の基本変換といったが、これはmod 2の上なので数倍にする必要性はなく、結局のところある行 or 列を別のに足すことを繰り返すことである。(XORによる行列の特徴でもあり、これを利用して実装はスマートに書ける)
行列の基本変換を施すことで、逆三角行列という形に持っていくことができる。これは以下のような形で、

f:id:Sen_comp:20201120040748j:plain

対角線上にはすべて1が乗っており、それ以外は0であるという性質を持つ。(右端の対角線が切れている部分は無視する)この性質から、 \vec{y}でその桁に+1(mod 2)をしたいときには、決まった基底を選ぶとできる」という重要な性質が導ける。

今まででは、いくつかの候補のうちから総当たりで2の累乗回最悪見る必要があったが、基底に整理して逆三角行列の形で見れば、基底を上から見て、採用or不採用を一意に選べるので、計算量は大きく改善したことになる。
これで掃き出し法を行った結果、新しく加えたいベクトルの行 or 列が行列の基本変換によって \vec{0}となっていたら、それは既存の基底で作れることを表していて、逆にならなかったら、既存のでは作れないということになる。(これが1さんの手番の時ならば1さんの勝利が確定し、0さんならばこれを基底として線形空間 Xに加えればよい)

ところで、もう1つ考慮するべき点がある。一般的には、行列の基本変換を施して、基底を1組作ったときには、「変換前で作れたすべてのベクトルと、各基底の任意の実数倍の和で作れるベクトルは全く同じ線形空間をなす」ということであるが、任意の実数倍というところと、今回の問題の各 A_iたかだか1回までしか使えないというところで少し違うのだ。

しかし、今回に関してはそれは安全である。なぜならば、mod 2の世界であるので、係数自体は整数である上に、0か1しか係数にありえないとわかる。これは、同じ数に対して、XORが2回したら0になることに起因する性質である。

なお、mod 2の上での線形代数は普通の線形代数と違って多くの便利な性質があり、計算もbit演算を用いて簡便と高速化ができるので、普通の線形代数計算ライブラリとは別個な実装がされていることが多い。

Gauss-Jordan の掃き出し法と、連立一次方程式の解き方 - けんちょんの競プロ精進記録

解法のまとめ

ここまでの話を整理すると以下のようになる。

  • 後ろから見ていく。
  •  S_i=0ならば、線形空間 X A_iをベクトル化したものを加える。加える際は、そのたびに基底を作る掃き出し法を行って逆三角行列を作る。
  •  S_i=1ならば、線形空間 X A_iをベクトル化したものが含まれるか(つまり作れるか)を判定し、作れない->1さんの勝ち、作れる->未定
  • これを計N回行い、それでも1さんの勝利が確定しない場合は、0さんが勝つ。

実装

掃き出し法によって規定を作る部分はこのように実装した。

vector<ll> V;//この線形空間に新た加わるベクトルが含まれているか?を計算するために行列の基本変形で対角線の片側だけに並ぶあの形に掃き出し法を使う。
//掃き出し法自体はXORなのでmod2の上でできるbit演算を行う。
auto get_MSB = [](ll x) {return x & (-x); };
auto contain_in_V = [&](ll new_v) {
	for (int i = 0; i < V.size(); i++) {
		if ((get_MSB(V[i]) & new_v))
			new_v ^= V[i];
	}
	//0になったら、既存の基底で作れちゃうということなので追加する必要なし。
	return new_v;
};
auto insert_to_V = [&](ll new_v) {
	ll ret = contain_in_V(new_v);
	if(ret == 0)return;
	V.push_back(ret);
};

ここでは先ほど解説では逆三角行列としたが、左右を反転した変則的な逆三角行列で考えている。

f:id:Sen_comp:20201120044449j:plain

この変則的な逆三角行列にMSB()という一番下の桁だけを立てるbit演算を駆使すると、一番右端のつまり対角線上に乗っている1のみが立つ値が得られる。新しく加えるnew_vのi桁目が1であるのならば、必ずこの基底を加えてi桁目を0にしないといけない。(^での演算部分)

contain_in_V()で得られた値が0であるのならば、加えたいnew_vはその線形空間に含まれるということであり、0でなければnew_vから抽出した基底が得られる。

insert_to_V()はその値に応じて線形空間に既定に挿入をする操作を行っているだけである。

ACソースコード
Submission #18054941 - AtCoder Grand Contest 045

一言

久しぶりに本腰を入れてがっつりした解説記事を書いた。6000字オーバーである。
AGC-Aに置く問題でも400点でもないだろ...初心者お断りコンテストだとしてもこの点数詐欺と難易度の置き方は悪意がすごい。
おまけに公式解説放送もないのでこの問題の解法を理解するのにかなり時間がかかった。

以上のところで誤りがあったらお手数ですがTwitterで連絡ください。

Android開発 for Kotlin 自分向けのメモ帳追加パック 動的な部分-暗黙的Intent

自分向けのメモ。たぶん新入生教育にも開発仲間にも役に立ちそう。(あくまで自分向けのsummaryだが)

動的な部分
sen-comp.hatenablog.com

続きを読む

SoundHound Programming Contest 2018 Masters Tournament 本戦 - B - Neutralize

https://atcoder.jp/contests/soundhound2018-summer-final/tasks/soundhound2018_summer_final_b

概要

長さNの数列{a}が与えられる。K<=NのKが与えられる。
あなたは次の操作を好きな回数だけ行うことができる。

  • 連続するK項を選び、それらの値をすべて0にする。

この時数列{a}の和の最大値を求めよ。

制約:1 <= K <= N <= 2 * 10^5, -10^9 <= A[i] <= 10^9

続きを読む

ABC172 - E - NEQ + アルゴリズムの応用問題例(グラフのK彩色の場合の数)

atcoder.jp

概要

N <= Mの数字N, Mが与えられる。2つの長さNの数列A, Bで、次の条件を満たすようなものが何通りあるかを求めよ。ただし、非常に大きくなる場合があるので、 10^9+7で割ったあまりを求めること。

  • AとBの要素は、[1, M]の任意の整数
  • A[i] != B[i] (1 <= i <= Nのすべてのi)
  • A[i] != A[j] (1 <= i < j <= Nのすべての(i, j)の組)

つまり、同じindexでのAとBの要素が共通ではないかつ、AもBも自身の要素では重複がないという条件下で、何通りの数列が作れるのかということである。

制約:1 <= N <= M <= 5 * 10^5

続きを読む