SRM614D1Med CycleColoring
ややこしすぎる…
問題概要(原文)
$N(1 \leq N \leq 50)$ 個のサイクルがある． $i$ 番目のサイクルは $V_i$ 個の頂点からなり， $0,1,\ldots,V_i -1$ の番号がついていて，隣り合う頂点同士は黒い色の辺でつながれている． $i$ 番目のサイクルの $f_i$ 番目と $i+1$ 番目のサイクルの $t_i$ 番目を赤い色の辺でつないで，より大きなサイクルを作る．
ここで，頂点を $K$ 種類の色で彩色する． 黒い辺の両端の頂点の色は異なり，赤い色の両端の頂点の色は同じという条件を満たす塗り分け方は何通りあるか？ MOD $10^9+7$ で求めよ．
考察
部分問題として以下の問題を考える．
- $N$ 個の頂点からなるパスがある．頂点を $K$ 色で彩色する． $1$ 番の頂点に $1$ 番の色を塗る．隣り合う頂点の色が全て異なるという条件を満たす塗り分け方は何通りあるか？ また， $N$ 番の頂点の色が $1$ 番かそうでないか，の $2$ つの条件を持つ．
これは以下のDPで解ける．
\[ \begin{aligned} dp_{i, \text{same}} & = dp_{i-1,\text{diff}} \\ dp_{i, \text{diff}} & = (K-1)dp_{i-1,\text{same}} + (K-2)dp_{i-1,\text{diff}} \end{aligned} \]
さて，赤い色の辺の両端の頂点の色は同じという条件について考えよう． $f_i$ と $t_{i-1}$ によって， $|t_{i-1}-f_i|$ 個の頂点からなるパスと $V_i- |t_{i-1}-f_i|$ 個の頂点からなるパスに分解できる．
ここでどのようにして全体の数え上げをするかというと， $t_N$ の色を $1$ 番としたときに， $f_1$ の色が $1$ であるような塗り方の通り数と $1$ でないような塗り方の通り数を求められればよい． $i$ 番のサイクルは $t_{i-1}$ と $f_i$ によって分解されるので，これらから適切な係数を求めて $f_i$ が $t_N$ と同じ色である(もしくはない)ような通り数を求めよう． 最終的に $f_N$ の色が $1$ であるような通り数を答えればよい．
ソースコード
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using Debug = System.Diagnostics.Debug;
using StringBuilder = System.Text.StringBuilder;
public class CycleColoring
{
public int countColorings(int[] size, int[] from, int[] to, int K)
{
//dp(i,0) i番目の色と1番目の色が同じ 通り数
//dp(i,1) i番目の色と1番目の色が違う 通り数
var dp = Enumerate(1000050, x => new ModInteger[2]);
dp[1][0] = 1;
dp[1][1] = 0;
for (int i = 2; i <= 1000010; i++)
{
dp[i][0] = dp[i - 1][1];
dp[i][1] = (K - 1) * dp[i - 1][0] + (K - 2) * dp[i - 1][1];
}
var n = size.Length;
var dp2 = new ModInteger[2] { K, 0 };
for (int i = 0; i < n; i++)
{
var f = from[i];
var t = to[(i + n - 1) % n];
var m = size[i];
var a = Math.Abs(t - f);
var b = m - a;
Debug.WriteLine("{0} {1}", a, b);
var all = dp[m][1];
var same = dp[a + 1][0] * dp[b + 1][0];
var diff = all - same;
var next = new ModInteger[2];
next[0] = dp2[0] * same + dp2[1] * diff * ModInteger.Inverse(K - 1);
next[1] = (dp2[0] + dp2[1]) * all - next[0];
dp2 = next;
}
return (int)dp2[0].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
#region Inverse
public partial struct ModInteger
{
static public ModInteger Inverse(ModInteger v)
{
long p, q;
ExGCD(v.num, Mod, out p, out q);
return new ModInteger(p % Mod + Mod);
}
static public long ExGCD(long a, long b, out long x, out long y)
{
var u = new long[] { a, 1, 0 };
var v = new long[] { b, 0, 1 };
while (v[0] != 0)
{
var t = u[0] / v[0];
for (int i = 0; i < 3; i++)
{
var tmp = u[i] - t * v[i];
u[i] = v[i];
v[i] = tmp;
}
}
x = u[1];
y = u[2];
if (u[0] > 0)
return u[0];
for (int i = 0; i < 3; i++)
u[i] = -u[i];
return u[0];
}
}
#endregion
コメント
- こういうのが自力で解けないのはダメ
