AI 人工智能产业园路口-----dp

北京市商汤科技开发有限公司建立了新的 AI 人工智能产业园，这个产业园区里有 nn 个路口，由 n - 1n−1 条道路连通。第 ii 条道路连接路口 u_iui 和 v_ivi。

每个路口都布有一台信号发射器，信号频段是 11 到 mm 之间的一个整数。

道路所连接的两个路口的发射信号叠加可能会影响道路的正常运行。具体地，如果第 ii 条道路连接的两个路口发射信号的频段分别为 aa 和 bb，那么 \gcd(a, b)gcd(a,b) 不能恰好等于道路的保留频段 w_iwi。每条道路的保留频段是唯一的，即不会与其余任何道路的保留频段相同。

你现在需要确定每个路口发射信号的频段，使其符合要求。

在开始之前，你想先算出共有多少种合法的方案。

由于答案可能很大，输出对 10 ^ 9 + 7109+7 取模的值作为答案。

输入格式

第一行，两个正整数 n, mn,m 分别代表路口数量和信号频段上限。

接下来 n - 1n−1 行，每行描述一条道路。第 ii 行有三个整数 u_i, v_i, w_iui,vi,wi 意义如上所述。

保证 1 \le n \le m, 1 \le u_i, v_i \le n, 1 \le w_i \le m1≤n≤m,1≤ui,vi≤n,1≤wi≤m。

输出格式

输出一个整数，代表合法方案的数量对 10 ^ 9 + 7109+7 取模的值。

数据范围

m \le 50m≤50
v_i = u_{i + 1} = u_i + 1vi=ui+1=ui+1 (1 \le i \lt n)(1≤i<n)

样例解释

所有合法的方案为 (2, 2, 1), (2, 2, 3), (3, 3, 1), (3, 3, 2), (3, 3, 3)(2,2,1),(2,2,3),(3,3,1),(3,3,2),(3,3,3)。

样例输入复制

样例输出复制

5

题解：在简单版本中，我们仅需要处理一条链上的情况。可用序列上的动态规划解决。 设a[i]为路口i与i-1相连道路的保留频段 。 令dp[j][k]为路口i获取的信号频段为j 的方案数，
易得转移方程
dp[i][j]=dp[i][j]+dp[i][k]  (k=1,2,3,4.....m)
最后输出dp[n][1]+dp[n][2]+dp[n][3]+....+dp[n][m]就是答案了

#include<iostream>

#define ll long long

#define mod 1000000007

using namespace std;

int n,m;

ll a[],dp[][];//dp[i][j]表示路口i的频段为j时的方案数

ll gcd(int a,int b)

{

    return b==?a:gcd(b,a%b);

}

int main()

{

    int x,y,w;

    cin>>n>>m;

    for(int i=;i<=n-;i++)

    {

        cin>>x>>y>>w;

        a[i]=w;

    }

    for(int i=;i<=m;i++)//初始化第一个路口

        dp[][i]=;

    for(int i=;i<=n;i++)

    {

        for(int j=;j<=m;j++)

        {

            for(int k=;k<=m;k++)

            {

                if(gcd(j,k)!=a[i-])

                    dp[i][j]=dp[i][j]+dp[i-][k];

                dp[i][j]=dp[i][j]%mod;

            }

        }

    }

    ll ans=;

    for(int i=;i<=m;i++)

    {

        ans=ans+dp[n][i];

        ans=ans%mod;

    }

    cout<<ans<<endl;

    return ;

}

// 3 3

// 1 2 1

// 2 3 2

巴特西