某 AtCoder 的 dp 场 | fa

~~Typical DP Contest，13 年的远古比赛了~~

比赛地址

本文为部分翻译+题解

谷的翻译大部分（所有正确使用了 $\LaTeX$ 的）是我搞的。很惭愧，就做了一点微小的贡献。

A - コンテスト

problem

有一场有 $n \ (1 \le n \le 100)$ 个问题的比赛，其中第 $i$ 个问题的分数为 $p_i \ (1 \le p_i \le 100)$。某个参赛者的分数为他做出的题目的分数之和。有多少种可能的得分？

solution

傻逼背包，连优化都不用的那种（

B - ゲーム

problem

Alice 和 Bob 在玩游戏。初始时有两座山，左边的山上有 $A$ 个物品，从上到下的第 $i$ 个价值为 $a_i$；右边的山上有 $B$ 个物品，从上到下的第 $i$ 个价值为 $b_i$。Alice 先手，Alice 和 Bob 交替进行操作，可行的操作如下：

如果两座山都空了，游戏结束。
如果只有某一座山空了，取走另一座山上的最上面的物品。
如果两座山都没有空，选择任意一座山，并取走其最上面的物品。

两人都想取得更大的价值。假设两人都采取最优策略，请求出 Alice 能取得的物品的价值总和。

输入的所有数字都是 $[1, 1000]$ 中的整数。

solution

考虑从终局向前逆推。设 $f_{i, j}$ 表示 $A$ 被取走第 $i \sim A$ 个物品， $B$ 被取走第 $j \sim B$ 个物品时的价值。

对 $i + j$ 为偶数/奇数，即 Alice/Bob 操作时分类转移：

$f_{i, j} = \begin{cases} \max(f_{i + 1, j} + a_i, f_{i, j + 1} + b_j) & , (i + j) \equiv 0 \pmod 2 \\ \min(f_{i + 1, j}, f_{i, j + 1}) & , (i + j) \equiv 1 \pmod 2 \end{cases}$

边界条件 $f_{i, B + 1} = f_{A + 1, j} = 0$。

答案即为 $f_{1, 1}$。总复杂度 $O(AB)$。

code

实现时要尤其注意边界情况。

int f[1003][1003];

int dp(int A, int* a, int B, int* b) {
  // a, b 下标均从 1 开始
  for (int i = A + 1; i; --i)
    for (int j = B + 1; j; --j) {
      if (i > A && j > B) continue;
      if ((i + j) & 1) {
        if (i > A)
          f[i][j] = f[i][j + 1];
        else if (j > B)
          f[i][j] = f[i + 1][j];
        else
          f[i][j] = std::min(f[i + 1][j], f[i][j + 1]);
      } else {
        if (i > A)
          f[i][j] = f[i][j + 1] + b[j];
        else if (j > B)
          f[i][j] = f[i + 1][j] + a[i];
        else
          f[i][j] = std::max(f[i + 1][j] + a[i], f[i][j + 1] + b[j]);
      }
    }
  return f[1][1];
}

C - トーナメント

problem

有 $2^k \ (1 \le k \le 10)$ 人参加一场锦标赛，这场锦标赛按以下的形式进行。

译者注：我知道可读性很差，但是很好理解，日语原题面就是这样的

第 1 轮，1 和 2，3 和 4，… 进行比赛。
第 2 轮，(1 和 2 的胜者)和(3 和 4 的胜者)，(5 和 6 的胜者)和(7 和 8 的胜者)，… 进行比赛。
第 3 轮，((1 和 2 的胜者)和(3 和 4 的胜者)的胜者)和((5 和 6 的胜者)和(7 和 8 的胜者)的胜者)，((9 和 10 的胜者)和(11 和 12 的胜者)的胜者)和((13 和 14 的胜者)和(15 和 16 的胜者)的胜者)，… 进行比赛。
重复相同的过程，直到第 $K$ 轮。

第 $K$ 轮结束后将会决出优胜者。如果第 $i$ 个人的 Elo Rating 为 $R_i \ (1 \le R_i \le 4000)$，求出每个人成为优胜者的概率。

规定：如果 Elo Rating 为 $R_P$ 的人 $P$ 和 Elo Rating 为 $R_Q$ 的人 $Q$ 对战，人 $P$ 的获胜概率为 $1 / (1 + 10^{(R_Q - R_P) / 400})$。假设不同的比赛的胜负是互相独立的。

solution

显然是道概率 dp（

设 $f_{k, i}$ 表示第 $k$ 轮比赛中第 $i$ 个人获胜的概率。不难得到这样的转移方程：

$f_{k, i} = f_{k - 1, i} \times \sum_{j \in S}{(f_{k - 1, j} \times P)}$

其中 $S$ 表示第 $k$ 轮中可能与 $i$ 比赛的人；$P$ 表示第 $j$ 个人此时获胜的概率。

边界条件 $f_{i, 0} = 1$。

答案即为 $f_{K, i} \ (1 \le i \le 2^K)$。总复杂度 $O(K \times 2^K)$。

code

using db = double;

int R[1<<10|1];
db f[11][1<<10|1];

inline db calc(int p, int q) {
  return 1 / (1 + pow(10., (R[q] - R[p]) / 400.));
}

int main() {
  int K, N;

  cin >> K;
  N = 1 << K;
  for (int i = 1; i <= N; ++i)
    cin >> R[i];
  for (int i = 1; i <= N; ++i)
    f[0][i] = 1;
  for (int k = 1, len; k <= K; ++k) {
    len = 1 << k;
    for (int i = 1, mn, mx, mid, l, r; i <= N; ++i) {
      db now = 0;
      mx = (i - 1) / len * len + len, mn = mx - len + 1;
      mid = ((mn + mx) >> 1) + 1;

      if (i < mid) l = mid, r = mx;
      else l = mn, r = mid - 1;
      // 此处的 l ~ r 为可能此时和第 j 个人比赛的编号区间

      for (int j = l; j <= r; ++j)
        now += f[k - 1][j] * calc(i, j);
      f[k][i] = now * f[k - 1][i];
    }
  }
  for (int i = 1; i <= N; ++i)
    printf("%.9lf\n", f[K][i]);
  return 0;
}

D - サイコロ

problem

将六个面的骰子掷 $N \ (1 \le N \le 100)$ 次，求每一次掷得的点数的乘积是 $D \ (1 \le D \le 10^{18})$ 的倍数的概率。

solution

考虑骰子掷出点数的乘积的质因子只可能有 $2, 3, 5$。考虑直接从这三个因数进行转移。

设 $f_{i, a, b, c}$ 表示第 $i$ 次掷骰子后点数的乘积中因子 $2$ 有 $a$ 个，$3$ 有 $b$ 个，$5$ 有 $c$ 个的可能性。

直接枚举每次掷骰子的过程转移即可。

边界条件 $f_{0, 0, 0, 0} = 1$。

答案即为 $f_{N, a, b, c}$。总复杂度 $O(Nabc)$。

code

实现看了看霓虹国神仙 Suikaba 的（小声

这个 dp 数组甚至可以滚动数组压掉一维，不过这里没写。

变量名和上文略有不同。数组大小奇怪是因为是压着上界开的。

constexpr int s2[] = {0, 0, 1, 0, 2, 0, 1};
constexpr int s3[] = {0, 0, 0, 1, 0, 0, 1};
constexpr int s5[] = {0, 0, 0, 0, 0, 1, 0};

double f[101][61][39][27];

double dp(int N, long long D) {
  int d2 = 0, d3 = 0, d5 = 0;
  
  while (D % 2 == 0)
    D /= 2, ++d2;
  while (D % 3 == 0)
    D /= 3, ++d3;
  while (D % 5 == 0)
    D /= 5, ++d5;
  if (D != 1) return 0;

  f[0][0][0][0] = 1;
  for (int i = 0; i < N; ++i)
    for (int i2 = 0; i2 <= d2; ++i2)
      for (int i3 = 0; i3 <= d3; ++i3)
        for (int i5 = 0; i5 <= d5; ++i5)
          for (int j = 1, t2, t3, t5; j <= 6; ++j) {
            t2 = min(d2, i2 + s2[j]);
            t3 = min(d3, i3 + s3[j]);
            t5 = min(d5, i5 + s5[j]);
            f[i + 1][t2][t3][t5] += f[i][i2][i3][i5] / 6;
          }
  return f[N][d2][d3][d5];
}

E - 数

problem

求出在 $1 \sim N$ 中有多少个整数的数码和是 $D$ 的倍数。答案对 $10^9 + 7$ 取模。

solution

这里是一篇记忆化搜索实现数位 dp 的题解。

设 $f_{i, j}$ 为最低位到从低到高第 $i$，模 $D$ 余数为 $j$ 时的合法方案数。

考虑搜索转移，深搜函数原型 int dfs(int pos, int rem, bool lim)，其中 pos 表示当前在从低到高第 pos 位，要搜索的余数为 rem，是否贴紧原数上界（lim == 1/0）。转移时按照含义即可。

注意有些题目需要特判前导零、考虑连续的几位数等特殊情况（本题不需要）。

dp 数组初始值要为一个小于零的数（想一想，为什么？）

code

理论上记忆化搜索实现要比递推转移常数大一点，但就这题来看这份代码跑得比大多数递推还要快（

constexpr int mod = 1000000007;

int N, D, num[10003], f[10003][101];
std::string s;

int dfs(int pos, int rem, bool lim) {
  if (!pos) return !rem;
  if (!lim && f[pos][rem] != -1) return f[pos][rem];
  int mx = lim ? num[pos] : 9, ans = 0;
  for (int i = 0; i <= mx; ++i)
    ans = (ans + dfs(pos - 1, (rem + i) % D, lim && i == mx)) % mod;
  if (!lim) f[pos][rem] = ans;
  return ans;
}

int main() {
  std::cin >> D >> s;
  for (auto it = s.rbegin(); it != s.rend(); ++it)
    num[++N] = *it & 15;
  memset(f, -1, sizeof f);
  std::cout << dfs(N, 0, 1) - 1 << '\n';
  return 0;
}

F - 準急

problem

有一条有 $N$ 个站的电车线路。你要在这条线路上送外卖。

你需要在 $1$ 号站停靠，在 {$2$ 号站，…，$N - 1$ 号站} 的子集停靠，在 $N$ 号站停靠。
你不会在连续超过 $K$ 个车站停靠。

求有多少种可能的停靠方案数。答案对 $10^9 + 7$ 取模。

solution

设 $f_{i, 0/1}$ 表示前 $i$ 个车站不停靠/停靠的方案数。显然有 $f_{i, 0} = f_{i - 1, 0} + f_{i - 1, 1}$。

对于 $f_{i, 1}$，需要减去不合法的方案数，即前 $K - 1$ 个车站都停靠的方案数。显然这个等于 $f_{i - K, 0}$。

边界条件 $f_{0, 0} = f_{0, 1} = f_{1, 1} = 1, f_{1, 0} = 0$。

答案即为 $f_{N, 1}$。总复杂度 $O(N)$。

code

constexpr int mod = 1000000007;

int f[1000003][2];

int dp(int N, int K) {
  f[0][0] = f[0][1] = f[1][1] = 1;
  for (int i = 2; i < K; ++i)
    f[i][0] = f[i][1] = (f[i - 1][0] + f[i - 1][1]) % mod;
  for (int i = K; i <= N; ++i) {
    f[i][0] = f[i][1] = (f[i - 1][0] + f[i - 1][1]) % mod;
    f[i][1] = (f[i][1] - f[i - K][0] + mod) % mod;
  }
  return f[N][1];
}

G - 辞書順

problem

求字符串 $s \ (1 \le |s| \le 10^6)$ 的字典序第 $K \ (1 \le K \le 10^{18})$ 小的非空子序列或判断不存在。相同的子序列只计算一次。字符集小写拉丁字母。

solution

と，色々書いたけどわかりにくい解説だな…．
自分もかなり苦手な問題なので…．
—— Suikaba 的原话

看了 Suikaba 神仙的题解，尝试来自己胡一胡（

设 $\mathrm{nxt}_{i, c}$ 为 $s$ 中第 $i$ 个位置之后第一个出现 $c$ 的位置；$f_i$ 为使用第 $i$ 个位置的字符，其后子序列的个数。那么有

$f_i = 1 + \sum_{c \in |T|} f_{\mathrm{nxt}_{i, c}}$

其中 $T$ 表示字符集。加上的 $1$ 表示当前字符单独成串。

考虑如何找到字典序第 $K$ 小的集合。设一个向后跳的指针，初始指向字符串起始位置。从小到大枚举 $T$ 中的字符，向后边跳指针边统计答案即可。实现细节见代码。

code

char s[1000003];
int nxt[1000003][27];
long long K, f[1000003];

int main() {
  scanf("%s%lld", s + 1, &K);
  const int N = strlen(s + 1);
  std::fill(nxt[N + 1] + 1, nxt[N + 1] + 27, N + 1);
  for (int i = N; i >= 0; --i) {
    memcpy(nxt[i] + 1, nxt[i + 1] + 1, sizeof(int) * 26);
    f[i] = 1;
    for (int j = 1; j <= 26; ++j) {
      f[i] += f[nxt[i][j]];
      f[i] = std::min(f[i], K + 1);
    }
    nxt[i][s[i] & 31] = i;
  }

  bool g = 0;
  for (int i, p = 1; K > 0; ) {
    for (i = 1; i <= 26; ++i)
      if (f[nxt[p][i]] < K)
        K -= f[nxt[p][i]];
      else {
        --K;
        p = nxt[p][i] + 1;
        g = 1;
        putchar(i - 1 + 'a');
        break;
      }
    if (i > 26) break;
  }
  puts(g ? "" : "Eel");
  return 0;
}

H - ナップザック

problem

有 $U \ (1 \le U \le 100)$ 个物品，第 $i$ 个的质量、价值、颜色分别为 $w_i, v_i, c_i \ (1 \le w_i, v_i \le 10000, 1 \le c_i \le 50)$。有一个背包，能容纳总质量为 $W \ (1 \le W \le 10000)$，颜色种类数为 $C \ (1 \le C \le 50)$ 的物品。求能容纳的物品的最大总价值。

solution

设 $f_{i, j}$ 表示使用不超过 $i$ 种颜色，总质量为 $j$ 时的最大价值。

需要枚举颜色个数和所有颜色，以每个颜色为整体进行转移。

转移时直接套用 01 背包转移方程 $F_i = max{\{F_{i - w_j} + v_j\}}$ 即可。其中 $F$ 代表 $f$ 的第一维。

初始状态 $f_{i, j} = - \infty, f_{0, 0} = 0$。

答案即为 $\max{\{f_{C, i}\}}$。总复杂度 $O(UCW)$，不过常数很小。

code

using namespace std;

struct Node {
  int w, v;
};

int t[10003], f[53][10003];
vector<Node> z[53];

int main() {
  int N, W, C;

  cin >> N >> W >> C;
  for (int i = 1, w, v, c; i <= N; ++i) {
    cin >> w >> v >> c;
    z[c].push_back({w, v});
  }

  memset(f, 0xc0, sizeof f);
  f[0][0] = 0;
  for (int c = 1; c <= 50; ++c)
    if (z[c].size()) {
      for (int i = C; i; --i) {
        memcpy(t, f[i - 1], sizeof(int) * (W + 1));
        for (Node x : z[c])
          for (int j = W; j >= x.w; --j)
            t[j] = max(t[j], t[j - x.w] + x.v);
        for (int j = 0; j <= W; ++j)
          f[i][j] = max(f[i][j], t[j]);
      }
    }
  cout << *max_element(f[C], f[C] + W + 1) << '\n';
  return 0;
}

I - イウィ

problem

给定一个仅由字符 $\texttt{i}$ 和 $\texttt{w}$ 构成的字符串 $s \ (1 \le |s| \le 300)$。你可以进行若干次操作，每次从串中选取连续的三个字符 $\texttt{iwi}$ 并删除。删除后这三个字符的左侧和右侧会连接在一起，得到一个长度比原来小 $3$ 的新串。求可能的最大操作次数。

solution & code 1

设 $f_{l, r}$ 表示 $s$ 的子串 $s_{l..r}$ 的答案。这个可以直接枚举分界点 $m \in [l, r)$ 分治转移。

套上记忆化，总复杂度是 $O(n^2)$ 的。

int f[303][303];
std::string s;

int dfs(int l, int r) { // [l, r]
  if (r - l <= 1) return 0;
  if (f[l][r] != -1) return f[l][r];

  int ans = 0;
  for (int m = l; m < r; ++m) {
    ans = std::max(ans, dfs(l, m) + dfs(m + 1, r));
    if (s[l] == 'i' && s[m] == 'w' && s[r] == 'i')
      if (dfs(l + 1, m - 1) == m - l - 1 && dfs(m + 1, r - 1) == r - m - 1)
        ans = r - l + 1;
  }
  return f[l][r] = ans;
}

int solve() {
  memset(f, -1, sizeof f);
  std::cin >> s;
  return dfs(0, s.size() - 1) / 3;
}

solution & code 2

其实这题大可不必 dp。考虑删去一个串 $\texttt{iwi}$ 后当且仅当它的左侧或右侧是 $\texttt{i}$ 才有可能出现一个新的串 $\texttt{iwi}$。

可以首先删去所有的 $\texttt{iwii}$ 和 $\texttt{iiwi}$ 的子串 $\texttt{iwi}$。

总复杂度也是 $O(n^2)$，带一个很小的常数~~，具体多小取决于数据强度~~。

std::string s;

int solve() {
  std::cin >> s;
  const int N = s.size();

  for (std::string::size_type p = 0; ; )
    if ((p = s.find("iiwi")) != std::string::npos)
      s.erase(p + 1, 3);
    else if ((p = s.find("iwii")) != std::string::npos)
      s.erase(p, 3);
    else break;

  for (std::string::size_type p = 0; (p = s.find("iwi", p)) != std::string::npos; )
    s.erase(p, 3);

  return (N - s.size()) / 3;
}

J - ボール

problem

有 $N \ (1 \le N \le 16)$ 个物品，其中第 $i$ 个在 $x_i \ (0 \le x_i \le 15)$ 坐标处。向坐标 $x$ 扔球时，分别有 $\frac{1}{3}$ 的概率击中坐标 $x - 1, x, x + 1$ 中的一个；如果打中的坐标上有物品，将其打倒。求出在最优策略下期望扔球多少次将所有物品打倒。保证 $x_i$ 两两不同。

赛时补充：每次扔球时可以先看到上一次扔球击中的位置再决定向哪里扔球。

problem

看到这个数据范围，盲猜状压。

设 $E(S)$ 为状态 $S$ 时的期望次数。考虑如何转移。一般这种题需要列出一个关于 $E(S)$ 的方程，把它反解出来。

考虑向 $x$ 扔球的情况，能列出这样的一个方程：

$E(S) = 1 + \sum{(P(u) \times E(T))} + (1 - \sum{P(u)}) \times E(S)$

其中 $P(x) = \frac{1}{3}$ 表示击中坐标 $x$ 的概率，$u \in \{x - 1, x, x + 1 \}$，T = S & ~u。化简可得

$E(S) = \frac{1 + \sum{(P(u) \times E(T))}}{\sum P(u)}$

就可以枚举 $x$ 进行转移了。

显然可以记忆化一下。设 $f_S = E(S)$，初始状态 $f_0 = 0$。

答案即为 $E(S)$。总复杂度 $O(N \times 2^N)$。

code

代码可能换了一些奇怪的写法，但是跟上面式子是等价的（

double f[1<<16|1];

double dfs(int S) {
  if (f[S] >= 0.) return f[S];

  double ans = 1 << 16, E;
  for (int x = 0, c; x < 16; ++x) {
    int T[] = {
      S & ~((1 << x) << 1),
      S & ~(1 << x),
      S & ~((1 << x) >> 1)
    };
    c = 0, E = 1.;

    for (int i = 0; i < 3; ++i)
      if (S != T[i])
        E += dfs(T[i]) / 3., ++c;
    ans = std::min(ans, 3 * E / c);
  }
  return f[S] = ans;
}

double solve() {
  int N, S = 0;
  scanf("%d", &N);
  std::fill(f + 1, f + (1 << 16), -1);
  for (int t; N; --N) {
    scanf("%d", &t);
    S |= 1 << t;
  }
  return dfs(S);
}

K - ターゲット

problem

对于一个含 $K$ 个圆的序列 $C_1, C_2, \cdots, C_K$，如果对于每个 $i$ 都有圆 $C_{i + 1}$ 严格位于圆 $C_i$ 的内部，那么它们可以成为一个大小为 $K$ 的靶子。

平面直角坐标系里有 $N \ (1 \le N \le 10^6)$ 个圆，第 $i$ 个的圆心为 $(x_i, 0) \ (1 \le x_i \le 10^9)$，半径为 $r_i \ (1 \le r_i \le 10^9)$。选出若干个圆并重新排列构成靶子，求出可能构成的靶子的最大大小。

solution

对于每个圆 $i$ 构造一个二元组 $(x_i + r_i, x_i - r_i)$，按升序排序，再对第二关键字求出最长下降子序列的长度就是答案。

想象一下一堆圆画在这里是什么样子的、取出合法的部分是什么样子的，这个就很显然了（

code

using namespace std;

int f[100003];
pair<int, int> p[100003];

int main() {
  int N, N_ = 1;

  cin >> N;
  for (int i = 1, x, r; i <= N; ++i) {
    cin >> x >> r;
    p[i] = {x + r, x - r};
  }
  sort(p + 1, p + N + 1);

  f[1] = -p[1].second;
  for (int i = 2; i <= N; ++i)
    if (f[N_] < -p[i].second) f[++N_] = -p[i].second;
    else *lower_bound(f + 1, f + N_ + 1, -p[i].second) = -p[i].second;
  printf("%d\n", N_);
  return 0;
}

L - 猫

problem

有 $N \ (1 \le N \le 1000)$ 只猫，猫 $i$ 和猫 $j$ 的友好值为 $z_{i, j} \ (1 \le z_{i, j} \le 1000)$。猫的幸福度是与距离不超过 $1$ 的所有猫的友好值之和。把猫按照 $1 \sim N$ 的顺序置于一条线上（设猫 $i$ 的坐标为 $x_i$，则 $\forall i \in [1, N), x_i < x_{i + 1}$）。$x_i$ 可以为任意实数。求猫的幸福度之和的最大值。

保证 $z_{i, i} = 0, z_{i, j} = z_{j, i}$。

solution

设 $f_{i, j} \ (j \le i)$ 表示猫 $j$ 和猫 $i$ 在 $1$ 距离以内时前 $i$ 只猫的最大幸福度（两两之间计算一次）。则

$f_{i, j} = \max_{k = 1}^j{\{f_{i - 1, k}\}} + \sum_{l = j}^i z_{i, l}$

这个转移是 $O(N)$ 的，太慢了，要想办法优化掉。

令 $\mathrm{mx}_{i, k} = \max_{k = 1}^j{\{f_{i - 1, k}\}}, s_{i, j} = \sum_{k = j}^i z_{i, k}$，则 $f_{i, j} = \mathrm{mx}_{i, j} + s_{i, i} - s_{i, j - 1}$，转移成了 $O(1)$ 的。

答案即为 $2 \times \max{\{f_{N, i}\}}$。总复杂度 $O(N^2)$。

code

这里把三个数组都压了一维。其中 $\mathrm{mx}$ 先使用 $\mathrm{mx}_{i}$ 而后统计 $\mathrm{mx}_{i + 1}$。

注意这个写法下 $\mathrm{mx}_{i, 0}$ 要初始化成负无穷大。

这份代码目前在 AtC 是时间并列第一。空间有神仙用 std::vector 卡到 256KB 的，实在卡不过（

听说有写法还能省掉一个数组，不管了不管了.jpg

int s[1003], mx[1003], f[1003];

int solve() {
  int N;

  cin >> N;
  mx[0] = -0x3f3f3f3f;
  for (int i = 1; i <= N; ++i) {
    for (int j = 1; j <= N; ++j)
      cin >> s[j], s[j] += s[j - 1];
    for (int j = 1; j <= i; ++j) {
      f[j] = mx[j] + s[i] - s[j - 1];
      mx[j] = std::max(mx[j - 1], f[j]);
    }
    mx[i + 1] = mx[i];
  }

  return *std::max_element((f + 1, f + N + 1) << 1);
}

M - 家

problem

一栋房子有 $H \ (2 \le H \le 10^9)$ 层，每层的结构相同，都有 $R \ (1 \le R \le 16)$ 个房间。每层的构造用矩阵 $g$ 表示。如果 $g_{i, j} = 1$，则房间 $i$ 和房间 $j$ 之间有一条双向通路。对于任意的 $h \ (1 < h \le H)$ 和 $r \ (1 \le r \le R)$，可以通过 $h$ 层房间 $r$ 下楼到 $h - 1$ 层房间 $r$，不能上楼。求从 $H$ 层房间 $1$ 到 $1$ 层房间 $1$ 的不自交的路径条数。

保证 $g_{i, j} \in \{0, 1\}, g_{i, i} = 0, g_{i, j} = g_{j, i}$。答案对 $10^9 + 7$ 取模。

solution

~~看到大得离谱的 $H$ 直接推测矩阵+快速幂相关，看到小得离谱的 $R$ 直接推测状压相关~~

设矩阵 $M_{i, j}$ 表示在同一层中房间 $i$ 到房间 $j$ 的不自交的路径数。

这个可以状压求，设 $f_{s, i, S}$ 为从房间 $s$ 出发，经过总点集为 $S$ 到达 $i$ 的不自交的路径数。直接枚举转移没啥问题。那么 $M_{s, i} = \sum{f_{s, i, T}}$。

初始状态 $f_{i, s, 2^s} = 1$。

答案即为 $(M^H)_{0, 0}$。总复杂度 $O((2^R + \log H)R^3)$，时限 8s 足够了。

code

对于每个 $s$，$f$ 后两维的值互相独立，可以直接去掉第一维。

constexpr int mod = 1000000007;

inline int _Add(int m, int n) {
  return (m + n) % mod;
}

inline void Add(int &m, int n) {
  m = _Add(m, n);
}

struct Matrix {
  int S, z[17][17];

  Matrix(int _S, bool e=0); // e=1 时构造单位矩阵
  Matrix operator*(Matrix rhs);
  friend Matrix operator^(Matrix b, int p);
};

int H, R, z[17][17], f[16][1<<16|1];

int main() {
  std::cin >> H >> R;
  Matrix M(R);
  for (int i = 0; i < R; ++i)
    for (int j = 0; j < R; ++j)
      std::cin >> z[i][j];

  for (int s = 0; s < R; ++s) {
    memset(f, 0, sizeof f);
    f[s][1 << s] = 1;
    for (int S = 0; S < 1 << R; ++S)
      for (int i = 0; i < R; ++i)
        if (f[i][S]) for (int j = 0; j < R; ++j)
          if (!((S >> j) & 1) && z[i][j])
            Add(f[j][S | (1 << j)], f[i][S]);
    for (int i = 0; i < R; ++i)
      M.z[s][i] = std::accumulate(f[i], f[i] + (1 << R), 0, _Add);
  }
  std::cout << (M ^ H).z[0][0];
  return 0;
}

N - 木

problem

给定一棵 $N \ (1 \le N \le 1000)$ 个点的树。现在你有 $N$ 个点，需要重新画出这棵树。要求在连边过程中仍然是一棵树。求加边的方案数。

solution

是看的这个神仙的题解。

显然可以枚举每个点树形 dp 一遍。假设现在 dfs 到了点 $u$，考虑怎么转移。

设 $f_u$ 为以 $u$ 为根的子树的方案数，$s_u$ 为这棵子树中有多少条边。

从 $u$ 的儿子向上转移。假设现在处理到 $v$，需要在当前的加边序列中相对顺序不变地加入 $v$ 子树中的边。也即 s[u] += s[v], f[u] = f[u] * f[v] * C(s[u], s[v])。

最终答案是以每个点为根时的答案总和的一半，因为每条边会被两个端点计算一次，导致方案两两本质相同。

预处理出组合数，总复杂度 $O(n^2)$。

code

代码中 siz[] 即为上文的 $s$。

constexpr int mod = 1000000007, inv2 = 500000004;

int f[1003], siz[1003], head[1003], C[1003][1003];
struct Edge { int nxt, to; } e[2003];

void dfs(int u, int t) {
  f[u] = 1, siz[u] = 0;
  for (int i = head[u], v; i; i = e[i].nxt) {
    if ((v = e[i].to) == t) continue;
    dfs(v, u);
    siz[u] += siz[v];
    f[u] = 1ll * f[u] * f[v] % mod * C[siz[u]][siz[v]] % mod;
  }
  ++siz[u];
}

int solve() {
  int N, ans = 0;

  cin >> N;
  for (int i = 1, u, v; i < N; ++i) {
    cin >> u >> v;
    addEdge(u, v), addEdge(v, u);
  }

  for (int i = 1; i <= N; ++i) {
    C[i][0] = C[i][i] = 1;
    for (int j = 1; j < i; ++j)
      C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
  }

  for (int i = 1; i <= N; ++i) {
    dfs(i, 0);
    ans = (ans + f[i]) % mod;
  }
  return 1ll * ans * inv2 % mod;
}

O - 文字列

problem

构造一个小写字母构成的字符串，其中字母 $\alpha$ 出现了 $z_\alpha \ (0 \le z_\alpha \le 10)$ 次，且相同字母不相邻。求构造方案数。答案对 $10^9 + 7$ 取模。

solution

抄了这里。

code

c++14。和题解的略有不同。

constexpr int mod = 1'000'000'007;

inline int _Add(int m, int n);
inline void Add(int &m, int n);

int z[27], f[27][263], C[263][263];

int main() {
  int N = 0;

  for (int i = 26, t; i; --i) {
    std::cin >> t;
    if (t) z[++N] = t;
  }
  for (int i = 0; i <= 260; ++i) {
    C[i][0] = C[i][i] = 1;
    for (int j = 1; j < i; ++j)
      C[i][j] = _Add(C[i - 1][j - 1], C[i - 1][j]);
  }

  int l = z[1];
  f[1][z[1] - 1] = 1;
  for (int i = 2; i <= N; ++i) {
    for (int k = 0; k < l; ++k)
      for (int b = 0; b <= std::min(z[i], k); ++b)
        for (int a = 0, j; a + b <= z[i] && a <= l + 1 - k; ++a) {
          j = k - b + z[i] - a - b;
          Add(f[i][j], 1ll * f[i - 1][k] * C[k][b] % mod * C[l + 1 - k][a] % mod * C[z[i] - 1][a + b - 1] % mod);
        }
    l += z[i];
  }
  std::cout << f[N][0] << '\n';
  return 0;
}

P - うなぎ

problem

有一棵 $N \ (1 \le N \le 1000)$ 个点的树，第 $i$ 条边连接 $a_i$ 和 $b_i$。求出有多少种方案能够选出包含 $K \ (1 \le K \le 50)$ 条互不相交的路径的集合。注意集合是无序的。

此处两条路径不相交定义为两条路径的点集的交集为端点的并集的子集。