小D的剧场_牛客博客

链接：https://ac.nowcoder.com/acm/contest/369/A
来源：牛客网

题目描述

若你摘得小的星星你将得到小的幸福

若你摘得大的星星你将得到大的财富

若两者都能摘得你将得到永远的愿望

摘星是罪孽的宽恕摘星是夜晚的奇迹

抓住它吧你所期望的那颗星

无法触及，因而耀眼

明明触及了，却还是耀眼

——《少女☆歌剧 Revue·Starlight》

题目描述

"我明白。"

作为这命运剧场永远的观众，小D一直注视着这片星光璀璨的舞台，舞台上，少女们的身姿演绎出了一幕幕动人的场景，令人回味无穷。

有的时候，小D也会自己写一些歌曲，来加入Starlight的剧本，使得剧本充满了新的生命力。

现在小D又要准备写乐谱了，小D写谱的方式比较独特。他会先写出一个按照音符出现顺序排成的序列，再进一步整合，每次整合会选取相邻的三个作为三***。整合次数无限。

小D选取的音符形如D5 F6这种形式，例如D5表示D大调sol（这里不考虑升降音）为了方便生成乐谱，他将这些音符进一步转化了，小D给C D E F G A B重新编号成了1 2 3 4 5 6 7，之后新的音符编号生成方式应为(字母对应的标号-1)*7+数字，例如C7=(1−1)×7+7=7C7=(1−1)×7+7=7

但小D讨厌一些他所认为的不优美的***，因此他并不希望自己的谱子里面有可能出现这样的三***，也就说音符组成的序列里不应该存在他所讨厌的子段，假如C5 F1 A2这三个音符凑成的***小D不喜欢，那么序列里面就不能出现C5 F1 A2，C5 A2 F1，A2 C5 F1，A2 F1 C5，F1 A2 C5，F1 C5 A2这六种子段。

现在小D正在推算有多少合法的序列，答案对 109+7109+7 取模。

星屑飘洒的舞台上，可人绽放的爱之花，请努力让大家星光闪耀吧！

输入描述:

第一行为两个整数 n, q ，表示序列的长度和有多少***小D不喜欢.
接下来 q 行，每行三个整数 a, b, c ，表示小D不想出现的***

输出描述:

一行一个整数，表示答案

示例1

输入

复制

输出

复制

382785822

示例2

输入

复制

3 1
1 2 3

输出

复制

说明

一共有6种不合法的序列：

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

答案为493−6=117643493−6=117643

备注:

3≤n≤500,0≤q≤117649,1≤a,b,c≤49

思路：

令 dp[i][j][k] 表示目前序列放入到第 i 位，最后两个数字为 j , k 时的方案数，提前将不合法的子段标记

如果某个状态数 dp[i][j][k] 是已知的，只需要判断在它后面加上一个数字l，判断这种情况是否可行(即判断 j k l 三个数字的序列是否可行)，如果合法，dp[i][j][k] 就对 dp[i+1][k][l] 产生了贡献，所以针对每一个dp[i][j][k]计算贡献，dp[i+1][k][l] = ∑dp[i][j][k] (如果 j k l 序列合法)，所以ans等于所有放入了n位的方案数，。

code：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod = 1e9 + 7;
ll dp[505][50][50];
bool vis[50][50][50];//true表示不可行
int main()
{
	int n, q, a, b, c;
	scanf("%d%d", &n, &q);
	while (q--)
	{
		scanf("%d%d%d", &a, &b, &c);
		vis[a][b][c] = true;
		vis[a][c][b] = true;
		vis[b][a][c] = true;
		vis[b][c][a] = true;
		vis[c][a][b] = true;
		vis[c][b][a] = true;
	}
	//i=1时无意义
	for (int i = 2; i <= 2; i++)
	{
		for (int j = 1; j < 50; j++)
		{
			for (int k = 1; k < 50; k++)
				dp[i][j][k] = 1;
		}
	}
	for (int i = 3; i <= n; i++)
	{
		for (int j = 1; j < 50; j++)
		{
			for (int k = 1; k < 50; k++)
			{
				for (int l = 1; l < 50; l++)
				{
					if (vis[j][k][l])
						continue;
					dp[i][k][l] += dp[i - 1][j][k];
					if (dp[i][k][l] >= mod)
						dp[i][k][l] %= mod;
				}
			}
		}
	}
	ll ans = 0;
	for (int j = 1; j < 50; j++)
	{
		for (int k = 1; k < 50; k++)
		{
			ans += dp[n][j][k];
			if (ans >= mod)
				ans %= mod;
		}
	}
	printf("%lld\n", ans);
}