TCO2016R2AMed CliqueCuts

バグバグしい

問題概要(原文)

$N (N \leq 45)$ 頂点, $M$ 本の重みつきの辺からなるグラフが与えられる. 頂点を赤色か青色に塗り分ける.赤色で塗った頂点の誘導部分グラフはクリークになっていないといけない.

頂点の塗り方によってスコアが定まる.赤い頂点の集合を $V_{red}$,青い頂点の集合を $V_{blue}$,辺の両端の頂点が赤い辺の集合を $E_{red}$,辺の両端が青い頂点である辺の集合を $E_{blue}$ とする. 辺の重みを $w(e)$ とする.

このグラフのスコア $f(V_{red}, V_{blue}, E_{red}, E_{blue})$ は以下の式で定められる.

\[ f(V_{red}, V_{blue}, E_{red},E_{blue}) = \sum_{e_{r} \in E_{red}} w(e_{r}) - \sum_{e_{b} \in E_{blue}} w(e_{b}) \]

valid な塗り方全てについて,スコアを求め,その和を $\text{MOD} \; 10^9 + 7$ で求めよ.

考察

以降,赤色で塗った頂点の誘導部分グラフがクリークになるようなグラフのみ考える

辺の重みになっているのがヤバいので,頂点の重みにしたい気持ちになる. 辺の両端の頂点に辺の重みを加えよう. すると頂点 $v$ の重み $w(v)$ は $v$ に隣接する辺の重みの総和で表される.

このグラフのスコア $g(V_{red}, V_{blue}, E_{red}, E_{blue})$ は以下の式で定められる.

\[ \begin{aligned} g(V_{red}, V_{blue}, E_{red},E_{blue}) & = \sum_{e_{r} \in E_{red}} w(e_{r}) - \sum_{e_{b} \in E_{blue}} w(e_{b}) \\ & = 2f(V_{red}, V_{blue}, E_{red}, E_{blue}) \end{aligned} \]

こうすると,うまくキャンセルしあってくれるので,validなクリークを全て求めて,その得点の総和を求めてから $2$ で割ればよくなった. 頂点数が最大 $45$ と多いので,クリークを全て列挙はできない.

ここで $2^{\frac{N}{2}}poly(N)$ のサイズのクリークならばぎりぎり列挙可能であることを用いる. $N$ 個の頂点を適当に半分に分割したものを $V_1,V_2$ とする. 以下の $3$ つの関数を定義する.

\[ \begin{aligned} h(s) & = \begin{cases} 1 & (\text{induced subgraph of }s \text{ is clique})\\ 0 & (\text{otherwise}) \end{cases}\\ sum(s,V) & = \sum_{s^{\prime} \subseteq s} g(s^{\prime}, V \setminus s^{\prime}, \ldots )\\ cnt(s,V) & = \sum_{s^{\prime} \subseteq s} h(s^{\prime}) \end{aligned} \]

$h(s)$ は $s$ で表される頂点集合の誘導部分グラフがクリークをなすならば $1$ を,そうでなければ $0$ を返す関数である. $sum(s,V)$ は $V$ の部分集合 $s$ について, $s$ の部分集合 $s^{\prime}$ のスコアの総和を求める関数である. $cnt(s,V)$ は $V$ の部分集合 $s$ について, $s$ の部分集合 $s^{\prime}$ にいくつクリークをなすようなものがあるか数える関数である.

$2^{|V_{1}|}$ 通りのクリークを試して,その後,高速ゼータ変換っぽい感じでうまくbitDPをすると, $sum(s,V_1)$ と $cnt(s,V_1)$ の表を全て埋めることができる.

その後 $2^{|V_{2}|}$ 通りのクリークを全て試す. $s (s \subseteq V_{2})$ がクリークであるとする. $s$ と隣接する $V_{1}$ に含まれる頂点たちからなる極大集合を $t$ としよう.答えに $g(s, V_{2} \setminus s, \ldots)cnt(t,V_{1}) + sum(t,V_{1})$ を加算する.

このままだと,頂点を $1$ つも含まないというのが validなものとして含まれているのでこれを差し引いて, $2$ で割った値が求める値である.

ソースコード

using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using Debug = System.Diagnostics.Debug;
using StringBuilder = System.Text.StringBuilder;
public class CliqueCuts
{
    public int sum(int N, int[] a, int[] b, int[] c)
    {
        var g = Enumerate(N, x => 1L << x);
        var v = new ModInteger[N];
        for (int i = 0; i < a.Length; i++)
        {
            g[a[i]] |= 1L << b[i];
            g[b[i]] |= 1L << a[i];
            v[a[i]] += c[i];
            v[b[i]] += c[i];
        }
        var n = N / 2;
        var m = N - n;

        var sum = new ModInteger[1 << n];
        var pat = new ModInteger[1 << n];
        for (int mask = 0; mask < 1 << n; mask++)
        {
            long ok = mask;
            ModInteger u = 0;
            for (int i = 0; i < n; i++)
            {
                if ((mask >> i & 1) == 0) { u -= v[i]; continue; }
                u += v[i];
                ok &= g[i];
            }
            if (ok != mask) continue;
            sum[mask] += u;
            pat[mask] += 1;
        }
        for (int i = 0; i < n; i++)
            for (int mask = 0; mask < 1 << n; mask++)
                if ((mask >> i & 1) == 1)
                {
                    sum[mask] += sum[mask ^ (1 << i)];
                    pat[mask] += pat[mask ^ (1 << i)];
                }
        ModInteger ans = 0;
        for (long mask = 0; mask < 1L << N; mask += 1L << n)
        {
            long ok = mask;
            long fmask = (1L << n) - 1;
            ModInteger u = 0;
            for (int i = n; i < N; i++)
            {
                if ((mask >> i & 1) == 0) { u -= v[i]; continue; }
                u += v[i];
                ok &= g[i];
                fmask &= g[i];
            }
            if (ok != mask) continue;
            ans += pat[fmask] * u + sum[fmask];
        }
        foreach (var x in v) ans += x;
        ans *= (ModInteger.Mod + 1) / 2;
        return (int)ans.num;
    }

    static public T[] Enumerate<T>(int n, Func<int, T> f) { var a = new T[n]; for (int i = 0; i < n; ++i) a[i] = f(i); return a; }

}

#region ModNumber
public partial struct ModInteger
{
    public const long Mod = (long)1e9 + 7;
    public long num;
    public ModInteger(long n) : this() { num = n % Mod; if (num < 0) num += Mod; }
    public override string ToString() { return num.ToString(); }
    public static ModInteger operator +(ModInteger l, ModInteger r) { var n = l.num + r.num; if (n >= Mod) n -= Mod; return new ModInteger() { num = n }; }
    public static ModInteger operator -(ModInteger l, ModInteger r) { var n = l.num + Mod - r.num; if (n >= Mod) n -= Mod; return new ModInteger() { num = n }; }
    public static ModInteger operator *(ModInteger l, ModInteger r) { return new ModInteger(l.num * r.num); }
    public static ModInteger operator ^(ModInteger l, long r) { return ModInteger.Pow(l, r); }
    public static implicit operator ModInteger(long n) { return new ModInteger(n); }
    public static ModInteger Pow(ModInteger v, long k)
    {
        ModInteger ret = 1;
        var n = k;
        for (; n > 0; n >>= 1, v *= v)
        {
            if ((n & 1) == 1)
                ret = ret * v;
        }
        return ret;
    }
}
#endregion

コメント

  • 辺の重みを頂点の重みに変えると扱いやすくなる,ということがある
  • 高速ゼータ変換(の類),すごい