SRM489D1H Apple Trees
D1 Hardは険しいなぁ(詠嘆)
問題概要(原文)
$D$ 個の点が等間隔である．ここに $N$ 個の木を点のどこかに植える． $i$ 番の木は距離 $R_i$ 未満に他の木があってはならない．
そのような並べ方は何通りあるか？
考察
$D \leq 100000$ と $D$ は大きく， $N,R_i \leq 40$ と $N,R_i$ は比較的小さい． 後者に着目していこう．
$R_i$ の降順に見ていくことにすると，前の木との制約に違反することがなくなって都合がよくなるのでそうする．
突然だが以下のような問題を考える． いくつかの鎖が一列に並んでいる．以下のような操作を繰り返して，長さが $D$ 以下の一本の円環状の鎖になるようにしたい．そのような方法は何通りあるか？初めは長さ $0$ の鎖が $1$ 本ある
- 長さ $2(R_i - 1)$ の鎖をどこかに挿入する
- どこかの鎖の端に長さ $R_i - 1$ の鎖をつなげる
- 鎖の両端を選んでつなぐ(このとき，自分自身をつないでもよいし，隣り合う鎖の端をつないでもよい)
この問題はさっきの問題をもう少し簡単にした問題になっている．どういうことかというと， $N!$ 通りの並べ方について，可能な限り隣り合う木の距離を最小化したときに木によって(両端を除いて)網羅される区間の長さをうまく試していることになっている．
あとはどこに木を置くかを組合せを使って試す．これは網羅される長さが $L$ のとき $\binom{D-L}{N}$ 通りある．
計算量は $O(D+N^{3} R)$
ソースコード
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using Debug = System.Diagnostics.Debug;
using StringBuilder = System.Text.StringBuilder;
public class AppleTrees
{
public int theCount(int D, int[] r)
{
const int MAX = 80 * 40;
var dp = new ModInteger[MAX + 100, 45];
dp[0, 1] = 1;
foreach (var x in r.OrderByDescending(x => x))
{
var next = new ModInteger[MAX + 100, 45];
for (int i = 0; i < MAX; i++)
for (int j = 1; j < 42; j++)
{
next[i, j - 1] += dp[i, j] * j;
next[i + x - 1, j] += dp[i, j] * 2 * j;
next[i + 2 * (x - 1), j + 1] += dp[i, j] * j;
}
dp = next;
}
var fact = new ModInteger[200000];
var inv = new ModInteger[200000];
fact[0] = 1;inv[0] = 1;
for (int i = 1; i < 200000; i++)
{
fact[i] = fact[i - 1] * i;
inv[i] = ModInteger.Pow(fact[i], ModInteger.Mod - 2);
}
Func<int, int, ModInteger> binomial = (a, b) => a < 0 || b < 0 || b > a ? 0 : fact[a] * inv[a - b] * inv[b];
ModInteger ans = 0;
for (int i = 0; i <= MAX + 80; i++)
if (dp[i, 0].num != 0)
ans += dp[i, 0] * binomial(D - i, r.Length);
return (int)ans.num;
}
}
#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() { num = 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
コメント
- 効率のいい(まとめられる)形でうまく計算したあと，係数をかけていい感じにするやつ
- こういう系が尋常ではなくニガテなのでrng問題で修行したい
