商汤AI园区的n个路口（简单）

一道不错的练习动态规划的题目

题目来源：https://nanti.jisuanke.com/t/39261
感谢优秀博客：2019 计蒜之道 初赛 第一场

题目描述
北京市商汤科技开发有限公司建立了新的 AI 人工智能产业园，这个产业园区里有 n 个路口，由 n−1 条道路连通。第 i 条道路连接路口 $ u_i $ 和 $ v_i $
每个路口都布有一台信号发射器，信号频段是 1 到 m 之间的一个整数。
道路所连接的两个路口的发射信号叠加可能会影响道路的正常运行。具体地，如果第 i 条道路连接的两个路口发射信号的频段分别为 a 和 b，那么 gcd(a,b) 不能恰好等于道路的保留频段 $w_i$ 。每条道路的保留频段是唯一的，即不会与其余任何道路的保留频段相同。
你现在需要确定每个路口发射信号的频段，使其符合要求。
在开始之前，你想先算出共有多少种合法的方案。
由于答案可能很大，输出对 10 ^ 9 + 7取模的值作为答案。
输入格式
第一行，两个正整数 n, m 分别代表路口数量和信号频段上限。
接下来 n - 1 行，每行描述一条道路。第 i 行有三个整数 $u_i, v_i, w_i $,意义如上所述。
保证 $ 1≤n≤m,1≤u_i,v_i ≤n,1≤w_i≤m$。
输出格式
输出一个整数，代表合法方案的数量对 10 ^ 9 + 7取模的值。
数据范围
m≤50
$v_i = u_{i + 1} = u_i + 1 (1≤i<n)$
样例解释
所有合法的方案为 (2,2,1),(2,2,3),(3,3,1),(3,3,2),(3,3,3)。
样例输入
3 3
1 2 1
2 3 2
样例输出
5

——————————————————————————————————
优秀博客链接中讲解的言简意赅，我也只稍加赘述
题目分析
题目输入样例较小1≤n≤m≤50,且保证是一条链
很容易想到对每两个路口i和i+1，遍历a b，记录满足gcd(a,b)!=cost[i]的个数
动态规划的思想涌上心头

算法思想
dp[i][j]记录第i个路口频段为j时，前i-1个路段满足合法条件的方案数
依次枚举路口i和i-1的频段，算法复杂度$O(nm^2)$
最后 记为结果

——————————————————完整代码————————————————————

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>

using namespace std;

typedef long long ll;
int read(){
	int x = 0, f = 0;
	char ch = getchar();
	while(ch < '0' || ch > '9'){
		f |= (ch == '-');
		ch = getchar();
	}
	
	while(ch >= '0' && ch <= '9'){
		x = (x << 3) + (x << 1) + (ch-'0');
		ch = getchar();
	}
	return x = f ? -x : x;
}
int Gcd(int a, int b){
	if(!b)	return a;
	return Gcd(b, a%b);
}
const int mod = 1e9 + 7;
ll dp[55][55];
int cost[55];
int n, m;
int main(){
	n = read(); m = read();
	for(int i = 2, a, b, c; i <= n; ++i){
		a = read(); b = read(); c = read();
		cost[b] = c;
	}
	for(int i = 1; i <= m; ++i){
		dp[1][i] = 1;//初始化
	}
	for(int i = 2; i <= n; ++i){
		for(int j = 1; j <= m; ++j){
			for(int k = 1; k <= m; ++k){
				if(Gcd(k, j) != cost[i])
					dp[i][j] = (dp[i][j] + dp[i-1][k]) % mod;
			}	
		}
	}
	ll ans = 0;
	for(int i = 1; i <= m; ++i){
		ans = (ans + dp[n][i]) % mod;
	}
	printf("%lld\n", ans);
	return 0;
}