计蒜之道初赛1B

Posted on | Post modified:

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

题面

题意：给你一个长度为$n$的链，让你为每个点分配一个点权使得相邻两个点之间的$gcd$不等于边权，求方案数。要求是点权的范围是$[1,m]$。

思路：

令$dp_{ij}$表示第$i$个点选择权值为$j$的方案数，那么状态转移方程为

$dp_{i,j}=\sum_{k=1}^{m}dp_{i-1,k}[gcd(j,k)\neq w_{i}]$

复杂度$O(nm^2)$

code

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
#include<bits/stdc++.h>

using namespace std;
const int mod = 1e9+7;
const int N = 100;
int w[N];
long long dp[N][N];
int main(){
	int n,m;
	cin>>n>>m;
	int a,b,c;
	for(int i=1;i<=n-1;i++){
		cin>>a>>b>>c;
		w[b]=c;
	}
	memset(dp,0,sizeof(dp));
	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(j,k)!=w[i]){
					dp[i][j]=(dp[i][j]%mod+dp[i-1][k]%mod)%mod;
				}
			}
		}
	}
	long long ans=0;
	for(int i=1;i<=m;i++) ans=(ans%mod+dp[n][i]%mod)%mod;
	cout<<ans<<endl;
	return 0;
}