解説

最後の条件がなかなか見慣れないので、考えてみよう。
これは、全てのビットかかぶらず、かつ、下位a+b+cビットに全部集まっていることを示している。
なので、a+b+c個ある1をx,y,zに割り振っていく問題と捉えていこう。

2番目の条件x > y > zは、それぞれの最上位ビットだけを見れば条件を満たすかがわかる。
この最上位ビットだけを考えてやれば、他の部分は適当に分配できそう？
いや、全探索と言っても、a+b+c番目の1は、xが取る必要がある。
yの最上位ビットを全探索してやれば、良さそうか？
良さそうだな。

yの最上位ビットがyi番目のとき、
[a+b+c,yi)番目のビットはすべてxのものになる。
(yi,1]番目の1は、xyzのどれに振ってもx>y>zの条件は満たすので大丈夫。
あとは、a,b,c個になるように計算する必要がある。
すでにxは(a+b+c)-yi個とっているし、yは1個とっているのでそれは減らそう。

(yi-1)個をa個b個c個の3グループに分ける。
zの総和に関係してくるのは、(yi-1)個からc個とってくる部分。
あるビットが1になっている組み合わせは、(yi-2)!/{a!b!(c-1)!}である。
これはどのビットについても組み合わせは変わらない。
よって、(1+2+4+8+...+2^yi-1)*(yi-2)!/{a!b!(c-1)!}がyi固定としたときのzの取りうる値の総和になる。

int a, b, c;
Comb<mint, 301010> com;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> a >> b >> c;

    mint ans = 0;
    mint z_tot = 1, z_cur = 1;
    rep(yi, 2, a + b + c)
    {
        int aa = a - (a + b + c - yi);
        int bb = b - 1;
        int cc = c;
        if (0 <= aa and 0 <= bb) {
            ans += com.fac[yi - 2] / (com.fac[aa] * com.fac[bb] * com.fac[cc - 1]) * z_tot;
        }
        z_cur *= 2;
        z_tot += z_cur;
    }
    cout << ans << endl;
}

はまやんはまやんはまやん

hamayanhamayan's blog

MESE [yukicoder 895]

解説