NF

地方で働くプログラマ

ABC156復習

Linux

ABC156参加日記 - NF

ABC156のD復習。色々調べたり解説（公式＋有志）を読んで何とかACは出来だけど、個別の要素は理解できてないし、数学的知識が要求されるので自分からすると覚えゲー。

ところで、今回は解説がかなり丁寧だったように思います（あと名前が出るようになった）。前回かなり荒れてたけど競プロ古参の人は甘えだー言ってる人が多かったので改善ないかな、と思ってだけど、早速テコ入れが入ったようです。このフットワークの軽さは流石だと思います。あと解説者の名前出すことで一定の責任を負ってもらうっていうのもあるのかな…


Dの話に戻ります。コンテスト中に自分が取ったアプローチは、組み合わせnC1＋nC2＋…+nCi（i≦n）を計算しつつ、iにaかbが含まれる時は飛ばすという方法でした。これだと、今回nが最大10^9のため、組み合わせを毎回取るのは時間的に無理でした。あと問題を理解し損ねていて、本数にaまたはbが含まれてはいけないんだと思ってました。例えば、a=4,b=9なら前述のiは1,2,3,5,6,7,8,10,11,12,13,15,…みたいな（多分、最近DP問題が続いて復習してたので、「禁止された数字」とかを想定してしまった）。なので、まずはnまでの数でaまたはbを含まない数を探して…と考えてたのでまぁ全然ダメでした。


今回のポイントは、
１．「全ての組み合わせの合計」から、a本とb本からできる組み合わせを引くと回答になる。
２．「全ての組み合わせの合計」は(2^n-1)になるが、nの制約から普通には計算できない。これは「繰り返し二乗法」（自乗法？）で計算できる。
３．a本とb本の組み合わせも同じく普通に計算できないので、これも特別な計算方法を使う。
４．答えをmodした結果を出力する場合、途中計算でmodを取っていいし、むしろ積極的に使うことで大きい数に対しての計算をしなくて済む。


１．についてはこれは言われれば確かに。問題ちゃんと理解できればここまでは分かったかも。
２．で(2^n-1)になる理由も公式解説で分かりました。花が4種類（w,x,y,z）ある時、wを選ぶ(0)/選ばない(1)、xを選ぶ(0)/選ばない(1)、…とすると0/1のビット列になって、0000～1111の取りうる数が2^4となり、今回は0本が選べないので2^n-1になるわけですね。なるほど。「繰り返し二乗法」はあれですね、a^4はa^2×a^2であることを利用して計算回数を減らすようです。modで割る方法も込みで、この辺の解説が参考になりました。
[数学] n乗の計算 | maspyのHP
繰り返し自乗法 - sataniC++
ちなみに、参加日記で引用したけんちょんさんのブログですが、冒頭のサンプルが今回はそのまま使えない上、後半の説明が難しく今回は参考にできませんでした。


３．は正直ちゃんと理解できてないけど、上級者のACコードを参考に以下のような実装を使ってnCiを計算した。今後も組み合わせの問題が出たら使いまわしていきたい。

const long long MOD = 1000000007;
long long power(long a,long b)
{
   return (b)? (power(a*a%MOD,b/2)*(b%2?a:1)%MOD):1;
}
long long combination(long long n,long long k)
{
   long long x=1;
   long long y=1;
   for(int i=1; i<=k; i++)
   {
      x = x*(n-i+1) % MOD;
      y = y*i % MOD;
   }
   return x*power(y,MOD-2)%MOD;
}

あと高速化するには、下の記事のような工夫が必要らしい。
二項係数 mod 素数を高速に計算する方法 [累積和, フェルマーの小定理, 繰り返し二乗法, コンビネーション, 10^9+7] - はまやんはまやんはまやん


４．が今まで理解できてなかったけど、少しだけmodの考え方が分かった。「答えがデカいからmodしてね」って場合は途中計算もデカいパターンがあり、その時は一定のルールに従って途中でmodして良いということだった。これも証明は難しく、暗記問題ですね。てか世の中のABC参加者はこれ証明も理解してつかってるのかな…解説はこの辺が参考になりました。ありがたや。
「1000000007 で割ったあまり」の求め方を総特集！ 〜 逆元から離散対数まで 〜 - Qiita
【高校数学A】合同式の基本 a≡b (mod p) | 受験の月

足し算で試してみます。13+3をmod5する場合、16mod5は1。途中式でmodする場合、13mod5＝3、3mod5＝3なので答えは3+3＝6なので更にmodして1。本当だ！これは結構ビックリなんですがどうしてこうなるんだ。ちなみに引き算の場合は注意が必要らしく、例えば11-3をmod5する場合、8mod5は3ですが、11mod5＝1、3mod5＝3なので、1-3で答えは-2。…ではなく、負の値になった時はmodする値を足して-2+5＝3にするようです。AC者のコードを見ると、最後の出力で以下のようにしてました。なるほど…

   std::cout << (ans%MOD+MOD) % MOD << std::endl;


という訳で久々にちゃんと復習できました。ってたった1問だけど。ちなみに、前回・前々回の復習は未だに理解できず日記としてかけてないです。年度内には何とか…


ところで奈央ぼうが可愛いんですけど。