出题人题解 | #小D的剧场#

原题解链接：https://ac.nowcoder.com/discuss/154293

令 $d{p}_{i,j,k}dp\_\{i,j,k\}$表示目前序列放入到第$ii$位，最后两个数字为$j,kj,k$时的方案数，提前将不合法的子段标记

转移方程为

$d{p}_{i,k,l}={\sum }_{j=1}^{49}{\mathrm{can}}_{}\times d{p}_{i-1,j,k}d\; p\_\{i,\; k,\; l\}=\backslash sum\_\{j=1\}^\{49\}\; \backslash operatorname\{can\}\_\{j,\; k,\; l\}\; \backslash times\; d\; p\_\{i-1,\; j,\; k\}$

$cancan$为$00$表示不合法，$11$表示合法。

时间复杂度 $O(49^{3}n)O(49^3n)$。

#include <bits/stdc++.h>
using namespace std;
typedef long long lo;
const lo mo = 1e9 + 7;
lo lx, ly, lz, n, q, f[512][64][64], ans; bool can[64][64][64];
int main() {
  for (int i = 0; i < 50; ++i)
    for (int j = 0; j < 50; ++j)
      for (int k = 0; k < 50; ++k) can[i][j][k] = 1;
  scanf("%lld%lld", &n, &q);
  for (int i = 1; i <= q; i ++)
    scanf("%lld%lld%lld", &lx, &ly, &lz), can[lx][ly][lz] = can[lx][lz][ly] = can[ly][lx][lz] = can[ly][lz][lx] = can[lz][lx][ly] = can[lz][ly][lx] = 0;
  f[0][0][0] = 1;
  for (int i = 1; i <= n; i ++) {
    for (int j = 0; j < 50; j ++)
      for (int k = 0; k < 50; k ++)
        for (int l = 1; l < 50; l ++) f[i][k][l] = (f[i][k][l] + can[j][k][l] * f[i - 1][j][k]) % mo;
  }
  for (int i = 1; i < 50; i ++)
    for (int j = 1; j < 50; j ++) ans = (ans + f[n][i][j]) % mo;
  printf("%lld", ans);
  return 0;
}