デラノイ数に関するメモ

デラノイ数って?

D(n,m):= (0,0)から(n,m)まで次の3つの移動方法を使って移動する方法の通り数

  • (x,y) から (x+1, y) (以降「縦」と表現)
  • (x,y) から (x, y+1) (以降「横」と表現)
  • (x,y) から (x+1, y+1) (以降「斜め」と表現)

漸化式

 D(n,m) = \begin{cases} 1 &(n=0 \lor m=0) \\ D(n-1, m-1) + D(n-1,m)+D(n,m-1)&(otherwise) \end{cases}

表現方法その1

k を「斜めを使う回数」とする。

k を固定すると，縦 n-k回，横 m-k回，斜め k回を並び替えるので通り数は \binom{n+m-k}{n}\binom{n}{k}。

これをすべての k について足し合わせて

D(n,m) = \displaystyle \sum_{k=0}^{\min(n,m)} \binom{n+m-k}{n}\binom{n}{k}

となる。

表現方法その2

「斜め」のことはおいておいて， n個の「縦」と m個の「横」を並び替えることを考える。

k を「『縦横』と並ぶ回数」とする。

k を固定すると，まず n個の「縦」と m個の「横」を並び替えたときにちょうど k回「縦横」という連続部分列が現れる通り数は \binom{n}{k}\binom{m}{k}となる*1。

また， k個の「縦横」それぞれについてそのまま進むか「斜め」に進むかを選ぶとすると選び方は 2^k 通りある。

これをすべての k について足し合わせて

D(n,m) = \displaystyle \sum_{k=0}^{\min(n,m)} \binom{n}{k}\binom{m}{k}2^k

となる。

この2つ，本当にイコール?

n \leq mとしても一般性を失わない。このとき \min(n,m) = nとなる。

D(n,m) = \displaystyle \sum_{k=0}^{\min(n,m)} \binom{n}{k}\binom{m}{k}2^k

の kを lに置き換えて \min(n,m) = nを適用すると

D(n,m) = \displaystyle \sum_{l=0}^{n} \binom{n}{l}\binom{m}{l}2^l

= \displaystyle \sum_{l=0}^{n} \binom{n}{l}\binom{m}{l} \sum_{k=0}^{l} \binom{l}{k}

= \displaystyle \sum_{l=0}^{n} \sum_{k=0}^{l} \binom{n}{l}\binom{m}{l} \binom{l}{k}

= \displaystyle \sum_{k=0}^{n} \sum_{l=k}^{n} \binom{n}{l}\binom{m}{l} \binom{l}{k}

と書き換えられる*2。あとは

\displaystyle \sum_{l=k}^{n} \binom{n}{l}\binom{m}{l} \binom{l}{k} = \binom{n+m-k}{n}\binom{n}{k}

であることを示せればよい。ここで

\binom{n}{l}\binom{m}{l} \binom{l}{k} = \dfrac{n!m!l!}{l!(n-l)!l!{m-l}!k!(l-k)!}

= \dfrac{n!m!}{(n-l)!l!{m-l}!k!(l-k)!}

= \dfrac{n!(n-k)!m!}{k!(n-k)!l!{m-l}!(n-l)!(l-k)!}

= \dfrac{n!}{k!(n-k)!} \dfrac{(n-k)!}{(n-l)!(l-k)!}\dfrac{m!}{l!{m-l}!}

= \binom{n}{k}\binom{n-k}{n-l} \binom{m}{l}

なので

\displaystyle \sum_{l=k}^{n} \binom{n}{l}\binom{m}{l} \binom{l}{k} = \sum_{l=k}^{n} \binom{n}{k}\binom{n-k}{n-l} \binom{m}{l}

\displaystyle =　\binom{n}{k} \sum_{l=k}^{n} \binom{n-k}{n-l} \binom{m}{l}

となる。最後に

\displaystyle \sum_{l=k}^{n} \binom{n-k}{n-l} \binom{m}{l} = \binom{n+m-k}{n} *3

なので結果的に

\displaystyle \binom{n}{k} \sum_{l=k}^{n} \binom{n-k}{n-l} \binom{m}{l} = \binom{n}{k} \binom{n+m-k}{n}

とかける。よって

\displaystyle \sum_{k=0}^{n} \sum_{l=k}^{n} \binom{n}{l}\binom{m}{l} \binom{l}{k} = \sum_{k=0}^{n} \binom{n}{k} \binom{n+m-k}{n}

で，つまり

\displaystyle \sum_{k=0}^{\min(n,m)} \binom{n+m-k}{n}\binom{n}{k} = \sum_{k=0}^{\min(n,m)} \binom{n}{k}\binom{m}{k}2^k

となる。

なんでこんな記事書いたの?

Wikipedia にあまりにもサラッと書いてあって頭悩ませたのでメモです。

*1:「縦縦...縦」という長さ nの文字列においてそれぞれの文字の後のうち「横」が入る場所を k個選ぶ。同様に「横横...横」という長さ mの文字列においてそれぞれの文字の前のうち「縦」が入る場所を k個選ぶ。例えば (n,m,k)=(4,3,2)の状況で「縦v縦縦v縦」「横v横v横」と選んだとすると生成される文字列は「横縦横縦縦横縦」となる。

*2:これは表現方法その2について「斜め」の個数が同じものをまとめた表現になっている。

*3:ヴァンデルモンドの畳み込みって名前付いてるらしい。

Floor Sum を理解したい

おことわり

この記事は厳密性を保証しません。

Floor Sum とは？

\displaystyle \sum_{i=0}^{N-1} \lfloor \dfrac{A+Bi}{M} \rfloor を高速に求めるやつ(ただし N,M,A,B\in \mathbb{Z} で N,A,B \geq 0， M \gt 0)。

どういうアルゴリズムを使えばいいのか

まず， A = Q_A M+A'， B = Q_B M+B' として 0 \leq A' \lt M ， 0 \leq B' \lt M の状態を作り上げます。すると

\displaystyle \sum_{i=0}^{N-1} \lfloor \dfrac{A+Bi}{M} \rfloor

\displaystyle = \sum_{i=0}^{N-1} \lfloor \dfrac{Q_A M+A'+(Q_B M+B')i}{M} \rfloor

\displaystyle = \sum_{i=0}^{N-1} \left( Q_A + Q_B i + \lfloor \dfrac{A'+B'i}{M} \rfloor \right)

\displaystyle =\sum_{i=0}^{N-1} Q_A + \sum_{i=0}^{N-1} Q_B i + \sum_{i=0}^{N-1} \lfloor \dfrac{A'+B'i}{M} \rfloor

\displaystyle = N Q_A + \dfrac{N(N-1)}{2} Q_B + \sum_{i=0}^{N-1} \lfloor \dfrac{A'+B'i}{M} \rfloor

となります。 N Q_A と \dfrac{N(N-1)}{2} Q_B は簡単に求められるので， \displaystyle \sum_{i=0}^{N-1} \lfloor \dfrac{A'+B'i}{M} \rfloor の部分をうまく求めればいいです。

B'=0 のときは当然 N \lfloor \dfrac{A'}{M} \rfloor = 0 となる*1ので，以下では B'\neq 0 の場合について考えます。

ここで， \lfloor \dfrac{A'+B'i}{M} \rfloor \geq j となるような iの個数を jごとに数え上げることを考えます。

j は整数なので， \lfloor \dfrac{A'+B'i}{M} \rfloor \geq j と \dfrac{A'+B'i}{M} \geq j は同値であり，

j \leq \dfrac{A'+B'i}{M}

\iff{} Mj \leq A'+B'i

\iff{} Mj-A' \leq B'i

\iff{} \dfrac{Mj-A'}{B'} \leq i

\iff{} \lceil \dfrac{Mj-A'}{B'} \rceil \leq i

\iff{} \lfloor \dfrac{Mj+A'+B'-1}{B'} \rfloor \leq i

よって \lfloor \dfrac{A'+B'i}{M} \rfloor \geq j となるような iの個数は N - \lfloor \dfrac{Mj+A'+B'-1}{B'} \rfloor個あります。

これを 1から N' = \lfloor \dfrac{A'+B'(N-1)}{M} \rfloor まで足し合わせて

\displaystyle \sum_{i=0}^{N-1} \lfloor \dfrac{A'+B'i}{M} \rfloor \displaystyle = \sum_{j=1}^{N'} \left( N - \lfloor \dfrac{Mj+A'+B'-1}{B'} \rfloor \right) \displaystyle = \sum_{j=1}^{N'} N - \sum_{j=1}^{N'} \lfloor \dfrac{Mj+A'+B'-1}{B'} \rfloor

となります。ここで， j' = j - 1 という記号を導入すると

\displaystyle N'N - \sum_{j'=0}^{N'-1} \lfloor \dfrac{Mj'+M-A'+B'-1}{B'} \rfloor

となります。

つまり，結局のところ

\displaystyle \sum_{i=0}^{N-1} \lfloor \dfrac{A+Bi}{M} \rfloor

\displaystyle = N Q_A + \dfrac{N(N-1)}{2} Q_B + N'N - \sum_{j'=0}^{N'-1} \lfloor \dfrac{Mj'+M-A'+B'-1}{B'} \rfloor

となります。ここで， \displaystyle \sum_{j'=0}^{N'-1} \lfloor \dfrac{Mj'+M-A'+B'-1}{B'} \rfloor

の部分は元の問題と同じ構造をしているので再帰的に解けば問題が解けます。

再帰関数を作る

\displaystyle f(N,M,A,B) = \sum_{i=0}^{N-1} \lfloor \dfrac{A+Bi}{M} \rfloor とおきます。

するとさっきの式は

\displaystyle f(N,M,A,B) = N Q_A + \dfrac{N(N-1)}{2} Q_B + N'N - f(N',B',M-A'+B'-1,M)

と書き直せます。

計算量

雑に見積もります。

\displaystyle f(\cdot,M,\cdot,B) は \displaystyle f(\cdot ,B\% M,\cdot,M) を呼び出すので，だいたいユークリッドの互除法と同じくらいの計算量になることが分かります。よって，計算量は O(\log(B+M)) で抑えられそうだということが分かります。

いかがでしたか？

間違っている部分などがあれば教えて下さい。

*1: A'の定義から 0\leq A' \lt M です。

ABC231: G - Balls in Boxes

問題概要

1 から N までの番号がついた N 個の箱があり，箱 i (1\leq i \leq N) に入っているボールの数は A_i である。 N 個の数から等確率で 1 つ選んでボールを 1 足すという操作を K 回 繰り返す。箱 i (1\leq i \leq N) に操作後に入っているボールの数を B_i として \prod_{i=1}^{N} B_i の期待値はいくらか。

(問題文は https://atcoder.jp/contests/abc231/tasks/abc231_g に記載されている。)

制約

  • 1 \leq N \leq 1000
  • 1 \leq K \leq 10^9
  • 1 \leq A_i \leq 10^9 (1\leq i \leq N)

アイディア

あとで答えを N^K で割ることにして，すべての操作における \prod_{i=1}^{N} B_i の和を求めることを考える。

まず重要なのは，各操作における \prod_{i=1}^{N} B_i の総和を求めることは，各操作を終えた後に N 個の箱それぞれからボールを 1 つずつ取り出す方法を数えるのと同じである。そこで，操作前に箱に入っていたボールを赤色に，操作で入れるボールを白色に塗ることにする。このとき，最後に選んだボールのうち赤色に塗られたものを取り出した箱の添字の集合を R，白色に塗られたものを取り出した箱の添字の集合を Wとする。このとき R \cap W = \varnothingかつ R\cup W = \{ i\in \mathbb{Z}\,:\, (1\leq i \leq N)\}である。また，箱 iに入っている白色のボールの個数を D_iとする。 D_iに関して以下が成り立つ。

  • D_i \geq 0 (1\leq i \leq N)
  • D_i \geq 1 (i \in W)
  • \sum_{i=1}^{N} D_i = K

この状況に限定した場合における「操作後に N 個の箱それぞれからボールを 1 つずつ取り出す方法」は \left(\prod_{i\in W} D_i\right) \left( \prod_{i\in R} A_i \right) である。また，このような状況になる場合の数は \dfrac{K!}{\prod_{i\in W} D_i!} である。ところで，これらをかけ合わせると

\displaystyle \left(\prod_{i\in W} D_i\right) \left( \prod_{i\in R} A_i \right) \dfrac{K!}{\prod_{i=1}^{N} D_i!}

\displaystyle = \left( \prod_{i\in R} A_i \right) \dfrac{K! \prod_{i\in W} D_i}{\prod_{i=1}^{N} D_i!}

\displaystyle = \left( \prod_{i\in R} A_i \right) \dfrac{K!}{\left(\prod_{i\in W} (D_i-1)!\right) \left(\prod_{i\in R} D_i!\right)}

となる。ここで， Wを固定した場合のすべての適切な (D_1, D_2, \cdots, D_N)の組み合わせについて \dfrac{K!}{\left(\prod_{i\in W} (D_i-1)!\right) \left(\prod_{i\in R} D_i!\right)}の総和を s(W)とする。 s(W)が |W| *1にのみ依存することを示す。

今， C_i(1\leq i \leq N) を

  • C_i = D_i (i \in R)
  • C_i = D_i-1 (i \in W)

とおく。すると， \dfrac{K!}{\left(\prod_{i\in W} (D_i-1)!\right) \left(\prod_{i\in R} D_i!\right)}は \dfrac{K!}{\prod_{i=1}^{N} C_i!}と書き直せる。また， \sum_{i=1}^{N} C_i = ( \sum_{i\in R} D_i ) + ( \sum_{i\in W} (D_i-1) ) = \sum_{i=1}^{N} D_i - |W| = K-|W|であり， C_i \geq 0 (1\leq i \leq N)である。つまり， s(R)は \sum_{i=1}^{N} C_i = K-|W|， C_i \geq 0 (1\leq i \leq N)を満たすすべての (C_1, C_2, \cdots, C_N)の組み合わせについて \dfrac{1}{\prod_{i=1}^{N} C_i!}を求めその総和をとったものに s(W)をかけたものとなる。逆に， \sum_{i=1}^{N} C_i = K-|W|， C_i \geq 0 (1\leq i \leq N)を満たすすべての (C_1, C_2, \cdots, C_N)の組み合わせについて \dfrac{1}{\prod_{i=1}^{N} C_i!}の総和を取ると \dfrac{s(W)}{K!}となる。ところで，

\displaystyle \exp(x) = \sum_{i=0}^{\infty} \dfrac{x^i}{i!}

より

\displaystyle \exp(Nx) = \left(\sum_{i=0}^{\infty} \dfrac{x^i}{i!}\right)^N = \left(\sum_{i=0}^{\infty} \dfrac{x^i}{i!}\right) \left(\sum_{i=0}^{\infty} \dfrac{x^i}{i!}\right)\cdots \left(\sum_{i=0}^{\infty} \dfrac{x^i}{i!}\right)

となるが， exp(Nx)の x^{K-|W|}の係数がちょうど \dfrac{s(W)}{K!}となっている *2。 \exp(Nx)の x^{K-|W|}の係数を求めるには \exp(Nx)を {K-|W|}回微分してから x=0を代入して (K-|W|)!で割ればよく，実際にやると \dfrac{N^{K-|W|}}{(K-|W|)!}となる。よって \dfrac{s(W)}{K!} = \dfrac{N^{K-|W|}}{(K-|W|)!}なので s(W) = N^{K-|W|} \prod_{i=0}^{|W|-1} (K-i)となり， |W|にのみ依存することが示された。

これによって

\displaystyle \left( \prod_{i\in R} A_i \right) \dfrac{K!}{\left(\prod_{i\in W} (D_i-1)!\right) \left(\prod_{i\in R} D_i!\right)}

は

\displaystyle \left( \prod_{i\in R} A_i \right) N^{K-|W|} \prod_{i=0}^{|W|-1} (K-i)

と書き換えられる。結局求めたいものはすべての Wについてのこの総和である。ここでは |W|が同じものをまとめて計算することを考えると， |W|が同じであるすべての Wについて \prod_{i\in R} A_iの総和が求まればよく，これは簡単な O(N^2)のDPで可能である。

実装

まず dp(i,j)を「 i個目までの数から j個選ぶ際の選んだ数の積」の和としてこれを求める。初期状態は dp(0,0) = 1で，遷移は dp(i,j) = dp(i-1,j)+dp(i-1,j-1)\cdot A_i (ただし dp(\cdot, -1)=0とする)となる。

また， calc(i) := \prod_{j=0}^{i-1} (K-j)も求めておく。 calc(0) = 1, calc(i+1) = calc(i)\cdot(K-i)である。

そして \sum_{i=0}^{N} dp(N,N-i)\cdot calc(i)\cdot N^{K-i} を求め，最後に N^Kで割る。あるいは最初から \sum_{i=0}^{N} dp(N,N-i)\cdot calc(i)\cdot N^{-i} を求めてもよいかもしれない。

コード

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

const long long int MOD = 998244353LL;

long long int dp[1001][1001],calc[1001],A[1000];

long long int pow_binary(long long int x, long long int y){
    long long int ret = 1LL;
    while(y){
        if(y%2){
            ret *= x; ret %= MOD;
        }
        x *= x; x %= MOD;
        y /= 2LL;
    }
    return ret;
}

int main(void){
    int N,i,j;
    long long int K,perK,V=1LL,ANS=0LL;
    cin >> N >> K;
    perK = pow_binary(N,MOD-2);
    for(i=0; i<N; ++i){
        cin >> A[i]; A[i] %= MOD;
    }
    dp[0][0] = 1LL;
    calc[0] = 1;
    for(i=0; i<N; ++i){
        calc[i+1] = (calc[i]*(K-i))%MOD;
        for(j=0; j<=i; ++j){
            dp[i+1][j] += dp[i][j]; dp[i+1][j] %= MOD;
            dp[i+1][j+1] += (dp[i][j]*A[i])%MOD; dp[i+1][j+1] %= MOD;
        }
    }
    for(i=0; i<=N; ++i){
        calc[i] *= dp[N][N-i]; calc[i] %= MOD;
        calc[i] *= V; calc[i] %= MOD;
        ANS += calc[i]; ANS %= MOD;
        V *= perK; V %= MOD;
    }
    cout << ANS << endl;
    return 0;
}

(提出したものはこちら)

感想

結構悩んで面白かった。分かる人からしたら基礎中の基礎なんだろうけど。

*1: Wのサイズで，つまり白色に塗られた石の数。

*2: \left(\sum_{i=0}^{\infty} \dfrac{x^i}{i!}\right) \left(\sum_{i=0}^{\infty} \dfrac{x^i}{i!}\right)\cdots \left(\sum_{i=0}^{\infty} \dfrac{x^i}{i!}\right) を展開しようとしてみると分かるはず。

DDCC2020予選: E - Majority of Balls

問題概要

2N 個のボールがあり， N個は赤色で N個は青色である。

2N 個 のボールのうちの N個を指定してその N個のボールのうちどちらの色の方が多いか，という質問を 210 回まですることができる。

このとき， 2N 個のボールの色をすべて当てよ。

(問題文は https://atcoder.jp/contests/ddcc2020-qual/tasks/ddcc2020_qual_e に記載されている。)

制約

  • 1 \leq N \leq 99
  • Nは奇数
  • 210 回まで質問ができる

アイディア

f(i) := (ボールi, i+1, \cdots, i+N-1 を指定したときのクエリの返答) とする。

ここで f(1) = f(N+1) = c とすると，ボール 1,2,3,\cdots,N,N+1,N+2,\cdots,2Nの 2N個のボールでも色 cのボールが多いことになってしまうので矛盾する。よって f(1) \neq f(N+1) である。

このことから， f(p) \neq f(p+1)となる pが 1,2,\cdots,Nに存在する(もし \forall pに対して f(p)=f(p+1)であるとすると f(1)=f(2)=\cdots=f(N)=f(N+1)となり f(1) \neq f(N+1)と矛盾)。

このとき， f(p) \neq f(p+1)なので， f(p)=cとすると p, p+1, \cdots, p+N-1に含まれる色 cのボールの個数は \dfrac{N+1}{2}以上 N以下であり，よって p+1, p+2, \cdots, p+N-1, p+Nに含まれる色 cのボールの個数は \dfrac{N+1}{2}以上 N+1以下となる(ボール p+Nが c色ならば色 cのボールの個数は 1つ増え，それ以外の場合は変わらないため)。

次に， f(p+1)=\bar{c}とすると(ただし \bar{c}は cではない方の色)とすると， p+1, p+2, \cdots, p+Nに含まれる色 cのボールの個数は 0以上 \dfrac{N-1}{2}以下となるので， p, p+1, p+2, \cdots, p+Nに含まれる色 cのボールの個数は 0以上 \dfrac{N+1}{2}以下となる(ボール pが c色ならば色 cのボールの個数は 1つ増え，それ以外の場合は変わらないため)。

以上から， p, p+1, \cdots, p+Nに含まれる色 cのボールの個数は \dfrac{N+1}{2}以上 \dfrac{N+1}{2}以下となり，つまり p, p+1, \cdots, p+Nに含まれる cのボールの個数は \dfrac{N+1}{2}個，よって区間 [p,p+N]のボールは赤色と青色のボールを同数含む。

区間 [p,p+N]は両色のボールを同数ずつ含むので，この区間内のボールに関しては自身を除いた N個のボールをそれぞれ質問で投げればよい。

さらに， pと p+Nのボールの色は違うので(同じであれば f(p)=f(p+1)となるので矛盾)， [1,p] \cup [p+N,2N ]についても両色のボールを同数ずつ含むといえるので，この区間内のボールに関しても自身を除いた N個のボールをそれぞれ質問で投げればよい。

これが基本方針である。

高速化

f(p) \neq f(p+1) となる pを探すところで二分法を使えばこの部分での質問は log_2 N回程度におさまり，全体的な質問回数が 2N+log_2 N回程度となる。

実装

素直に実装するだけ。

コード

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

int N,RB='R'+'B';

string reply;
char getreply(){
    cin >> reply;
    return reply[0];
}

void sendquestion(int s){
    int i;
    cout << "?";
    for(i=0; i<N; ++i){
        cout << " " << s+i;
    }
    cout << endl; cout.flush();
}

char c,ans[225];

int main(void){
    int i,j,p,l,r,m;
    cin >> N;
    l = 1; r = N+1;
    sendquestion(1); c = getreply();
    while(r-l>1){
        m = (l+r)/2;
        sendquestion(m);
        if(c == getreply()){
            l = m;
        }else{
            r = m;
        }
    }
    p = l;
    for(i=p; i<=p+N; ++i){
        cout << "?";
        for(j=p; j<=p+N; ++j){
            if(i==j){
                continue;
            }
            cout << " " << j;
        }
        cout << endl; cout.flush();
        ans[i-1] = RB-getreply();
    }
    for(i=1; i<=N*2; ++i){
        if(p<=i && i<=p+N){
            continue;
        }
        cout << "?";
        for(j=1; j<=p; ++j){
            if(i==j){
                continue;
            }
            cout << " " << j;
        }
        for(j=p+N; j<=N*2; ++j){
            if(i==j){
                continue;
            }
            cout << " " << j;
        }
        cout << endl; cout.flush();
        ans[i-1] = RB-getreply();
    }
    cout << "! ";
    for(i=0; i<N*2; ++i){
        cout << ans[i];
    }
    cout << endl; cout.flush();
    return 0;
}

(提出したものはこちら)

感想

橙パフォうれしい

CODE FESTIVAL 2016 Grand Final: J - 123 Pairs

問題概要

1 から 2N までの 2N 個の数を 2 つずつ N 個のペアにするとき，差が 1 のペアが A 個，差が 2 のペアが B 個，差が 3 のペアが C 個あるようなペアの作り方は何通りあるか。

(問題文は https://atcoder.jp/contests/cf16-exhibition-final/tasks/cf16_exhibition_final_j に記載されている。)

制約

  • 1 \leq N \leq 5000
  • 0 \leq A, B, C
  • A + B + C = N

アイディア

まず，差が 1 のペアと差が 3 のペアは共に偶奇の異なる数同士がペアになるため，偶奇の一致する数同士がペアになることになる差が 2 のペアは偶数個である必要がある。つまり B \bmod 2 = 1 の場合答えは 0 となる。

以下 B \bmod 2 = 0 の場合のみを考え， b = \dfrac{B}{2} とする。

実は，このようなペアの作り方は以下の 4 種類のペアの組み合わせの並び替えで構成される。

  1. 差が 3 のペア 3 つが組み合わさっている。 (例: 1 - 4, 2 - 5, 3 - 6 )
  2. 差が 3 のペア 1 つの間に差が 1 のペアが 1 つ挟まっている。(例: 1 - 4, 2 - 3 )
  3. 差が 2 のペア 2 つの間に差が 3 のペアが 0 個以上挟まっている。(例: 1 - 3, 2 - 5, 4 - 7, 6 - 8 )
  4. 差が 1 のペア単独 。(例: 1 - 2 )

差が 3 であるような C 個のペアのうち，タイプ 1 とタイプ 2 の構成に関わるペアの個数をそれぞれ 3x, y とする。 このとき，タイプ 1，タイプ 2，タイプ 3，タイプ 4のペアの組み合わせはそれぞれ x, y, b, A-yである。よってペアの組み合わせの並び替え方は \dbinom{A+b+x}{x} \times \dbinom{A+b}{b} \times \dbinom{A}{y} であり， C-3x-y 個のペアのタイプ 3 への割り振り方は， C-3x-y 個の石と b-1 個の仕切りを並べることを考えて \dbinom{C-3x-y+b-1}{C-3x-y} であるので O(1) で求められる。 あとは考えられる x, y をすべて試せばよい。

実装

二項係数をメモ化再帰で実装すると楽かもしれない。

「 C-3x-y 個の石と b-1 個の仕切りを並べることを考えて」の部分で地味にバグらせやすいので注意。

コード

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

typedef long long ll;
const ll MOD = (ll)(1e9+7);

ll memo[5050][5050];
bool done[5050][5050];

ll comb(int n, int k){
    if(n < k){
        return 0ll;
    }
    if(done[n][k]){
        return memo[n][k];
    }
    done[n][k] = true;
    if(k==0 || k==n){
        return memo[n][k] = 1ll;
    }
    memo[n][k] = (comb(n-1,k-1)+comb(n-1,k))%MOD;
    return memo[n][k];
}

int main(void){
    int N,A,B,C,b,x,y,z,m;
    ll ans=0ll,tmp;
    cin >> N >> A >> B >> C;
    if(B&1){
        cout << 0 << endl;
        return 0;
    }
    b = B>>1;
    for(x=0; x*3<=C; ++x){
        m = min(A,C-x*3);
        for(y=0; y<=m; ++y){
            z = C - x*3 - y;
            tmp = comb(A+b+x,x);
            tmp *= comb(A+b,b); tmp %= MOD;
            tmp *= comb(A,y); tmp %= MOD;
            if(b){
                tmp *= comb(z+b-1,z); tmp %= MOD;
            }else if(z){
                tmp = 0ll;
            }
            ans += tmp; ans %= MOD;
        }
    }
    cout << ans << endl;
    return 0;
}

(提出したものはこちら)

感想

急に解法が降ってきて嬉しかったので共有しておきます。

ABC138: F - Coincidence

問題概要

Lと Rが与えられる。このとき L \leq x \leq y \leq R かつ ( y \bmod x ) = ( y \oplus x ) を満たす整数の組 (x, y)の個数を求めよ。

(問題文は https://atcoder.jp/contests/abc138/tasks/abc138_f に記載されている。)

制約

  • 1 \leq L \leq R \leq 10^{18}

アイディア

1 \leq x \leq y の条件下で (y \bmod x ) \leq (y - x ) \leq ( y \oplus x ) が成り立つことが証明できる。よって， ( y \bmod x ) = ( y \oplus x ) が成り立つときには必ず ( y - x ) = ( y \oplus x ) が成り立つ。また，このとき yを xを割ったときの商は 1となる。逆に， yを xを割ったときの商は 1であるとき (y \bmod x ) = ( y - x )が成り立つため，条件「 ( y \bmod x ) = ( y \oplus x )」は条件「 ( y - x ) = ( y \oplus x )かつ yを xを割ったときの商が 1」と言い換えられ，さらに 1 \leq x \leq yであるため条件「 yを xを割ったときの商が 1」は x \leq y \lt 2x と言い換えられ，最終的に「 x \leq yかつ \frac{y}{2} \lt x」となる。よって，条件をまとめると以下の5つである。

  • x \leq y
  • L \leq x
  • y \leq R
  • \dfrac{y}{2} \lt x
  • ( y - x ) = ( y \oplus x )

そして，実は ( y - x ) = ( y \oplus x )をあとは，上4つに関するフラグを持ちながら ( y - x ) = ( y \oplus x )を保つように遷移を行いつつ地道にDPを行えばよい。

2019/08/19追記: ( y - x ) = ( y \oplus x ) が成り立つとき x \leq y も成り立つため， x \leq y に関するフラグは不必要です。コード例では x \leq y に関するフラグを持たずに実装しています。

実装

dp(i,a,b,c,d,p) を上から i 桁目まで見てかつyの最後の桁が pであるときの組み合わせの個数とする。ただし， a,b,c,dはそれぞれ

  • a: x \leq y が確定しているかどうか
  • b: L \leq x が確定しているかどうか
  • c: y \leq R が確定しているかどうか
  • d: \dfrac{y}{2} \lt x が確定しているかどうか

を示すフラグである。

今見ている桁が上から i 桁目であるとし， L,R の上から i 桁目をそれぞれ l,r とし， x, y に付け加える桁を s, t とすると，

  • a が false でかつ s \gt t のとき x \leq y ではないことが確定するので NG
  • b が false でかつ l \gt s のとき L \leq x ではないことが確定するので NG
  • c が false でかつ t \gt r のとき y \leq R ではないことが確定するので NG
  • d が false でかつ p \gt s のとき \dfrac{y}{2} \lt x ではないことが確定するので NG
  • x = 1 かつ y = 0 のとき ( y - x ) = ( y \oplus x ) ではないことが確定するので NG

これらのケースを除外したあとで

  • e: a が true または s \lt t ならば true
  • f: b が true または l \lt s ならば true
  • g: c が true または t \lt r ならば true
  • h: d が true または p \lt s ならば true

として， dp(i+1,e,f,g,h,t) に dp(i,a,b,c,d,p) を足せばよい。

計算量は O(\log(R))であるが，定数が比較的重い。

2019/08/19追記: 先程のアイディアで追記したとおり，フラグ a は不必要であるため下の実装例では持っていない。また，下の実装例ではフラグ b, c, d をbitによって管理している。

コード

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

typedef long long ll;
const ll MOD = (ll)(1e9+7);

ll dp[63][8][2];

int main(void){
    int i,j,k,l,r,p,s,t;
    ll L,R,ans=0ll;
    dp[0][0][0] = 1ll;
    cin >> L >> R;
    for(i=0; i<60; ++i){
        l = (!!(L&(1ll<<(59-i)))); r = (!!(R&(1ll<<(59-i))));
        for(s=0; s<2; ++s){
            for(t=0; t<2; ++t){
                    if(s==1 && t==0){
                        continue;
                    }
                for(j=0; j<8; ++j){
                    for(p=0; p<2; ++p){
                        if((!(j&1)) && (l > s)){
                            continue;
                        }
                        if((!(j&2)) && (t > r)){
                            continue;
                        }
                        if((!(j&4)) && (p > s)){
                            continue;
                        }
                        k = 0;
                        if((j&1) || (l < s)){
                            k += 1;
                        }
                        if((j&2) || (t < r)){
                            k += 2;
                        }
                        if((j&4) || (p < s)){
                            k += 4;
                        }
                        dp[i+1][k][t] += dp[i][j][p];
                        dp[i+1][k][t] %= MOD;
                    }
                }
            }
        }
    }
    for(j=0; j<8; ++j){
        for(p=0; p<2; ++p){
            if(!(j&4)){
                continue;
            }
            ans += dp[60][j][p];
            ans %= MOD;
        }
    }
    cout << ans << endl;
    return 0;
}

(提出したものはこちら)

感想

コンテスト中に通せなくて少しショックだったけど自分で思いつけてよかった...

AGC033: C - Removing Coins

問題概要

N 頂点からなる木が与えられる。 i (1 \leq i \leq N-1) 番目の辺は a_i と b_i を結んでいる。

最初それぞれの頂点にコインが 1枚おいてある。高橋くんと青木くんはそれぞれコインが置いてある頂点 v を 1つ選びその頂点に置いてあるコインをすべて取り，そのあとすべてのコインを v に距離 1 だけ近づけるという操作を繰り返す。

操作ができなくなった人を負けとすると，お互いに最善を尽くしたときどちらが勝つかを求めよ。

(問題文は https://atcoder.jp/contests/agc033/tasks/agc033_c に記載されている。)

制約

  • 1 \leq N \leq 2\times 10^5
  • 1 \leq a_i \leq N (1 \leq i \leq N-1)
  • 1 \leq b_i \leq N (1 \leq i \leq N-1)
  • a_i \neq b_i
  • 与えられるグラフは木

アイディア

1回の操作でコインは選んだ頂点 vに少しずつ引き寄せられるので，葉となる頂点からはコインは出ていくが入ってこない。つまり， 1回の操作はグラフから葉となる頂点をすべて消す(ただし選んだ頂点 vについては葉であっても当然消されない)のと同値である。

ここで，木上の最長パスのうちの 1つ(このパスを Pとする)についてのみ考えることとする。この最長パスの端点を S, Tとすると Sか Tを選ぶとこのパスの長さは 1減り， S, T以外の頂点を選んだ場合についてはこのパスの長さは 2減ることになる。

次に， P上にない頂点について考える。葉ではない頂点を選ぶとき，すべての葉が消されるので， Pよりも長いパスができることはなく， Pのパスを 2減らすこととなる。また， S, Tのどちらかを選ぶときも同様に S, Tのうち選ばれなかった頂点とすべての葉が消されるので， Pよりも長いパスができることはなく， Pのパスを 1減らすこととなる。

さらに， P上にない葉を消すことを考えると，もしもその葉が Pとは別の最長パスの端点であったとしたらそのパスを新たに Pとして考えることができ(つまり Pの長さが 1だけ減る)，それ以外のときは Pより長いパスができることはないので結局 Pのパスを 2減らすこととなる。

以上のことから，1回の操作は Pの長さを 1または 2減らすことと同値であることが分かる。

実装

木の最長パスを一般に直径という。直径の長さ(及びその長さを持つパス)はどの頂点でもよいので頂点を1つ選び Vとし， Vから最も遠い頂点の 1つを Sとして， Sからもっとも遠い頂点の 1つを Tとすると， Sと Tを端点とするパスの長さと一致する。 Sと Tは簡単なBFSで求められるので，直径の長さは O(N)で求まる。

そして，直径の長さをもとに青木くんが勝つか高橋くんが勝つかは単純なメモ化再帰*1で求めることができる。この計算量は O(N)である。

よって全体的な計算量は O(N)である。

コード

#include <iostream>
#include <vector>
using namespace std;

const int INF = (1<<30);

vector<int> g[225816],q[2];
int dist[225816];
bool done[225816],memo[225816];

bool solve(int r){
    if(done[r]){
        return memo[r];
    }
    done[r] = true;
    if(r==0){
        memo[r] = true;
    }else if(r==1){
        memo[r] = false;
    }else{
        memo[r] = (!(solve(r-1)&&solve(r-2)));
    }
    return memo[r];
}

int main(void){
    int N,a,b,i,j,k;
    cin >> N;
    for(i=1; i<N; ++i){
        cin >> a >> b;
        --a; --b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    a = 0;
    for(k=0; k<2; ++k){
        fill(dist,dist+N,INF);
        q[k].push_back(a);
        dist[a] = 0;
        for(i=0; i<q[k].size(); ++i){
            a = q[k][i];
            for(j=0; j<g[a].size(); ++j){
                b = g[a][j];
                if(dist[b] > dist[a]+1){
                    dist[b] = dist[a]+1;
                    q[k].push_back(b);
                }
            }
        }
    }
    cout << ((solve(dist[a]))?"First":"Second") << endl;
    return 0;
}

(提出したものはこちら)

感想

コンテスト中に 800を通したので喜んでいたら任意人類が通していて「うーん」となってしまった。問題自体はとても綺麗で好き。

*1:なおメモ化再帰も実は必要ない。直径の長さを 3で割った余りが 1のときは後手必勝であり，それ以外の場合は先手必勝であることを示すことができる。