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
コメント
- 辺の重みを頂点の重みに変えると扱いやすくなる，ということがある
- 高速ゼータ変換(の類)，すごい
