企业官网建设流程全解析

P3914 染色计数

题目描述

有一颗N NN个节点的树，节点用1 , 2 , ⋯ , N 1,2,\cdots,N1,2,⋯,N编号。你要给它染色，使得相邻节点的颜色不同。有M MM种颜色，用1 , 2 , ⋯ , M 1,2,\cdots,M1,2,⋯,M编号。每个节点可以染M MM种颜色中的若干种，求不同染色方案的数量除以(10 9 + 7 10^9 + 7109+7)的余数。

输入格式

第1 行，2 个整数N , M N,MN,M。

接下来N NN行，第i ii行表示节点i ii可以染的颜色。第1个整数k i k_iki​，表示可以染的颜色数量。接下来k i k_iki​个整数，表示可以染的颜色编号。

最后N − 1 N - 1N−1行，每行2个整数A i , B i A_i,B_iAi​,Bi​，表示边( A i , B i ) (A_i,B_i)(Ai​,Bi​)。

输出格式

1 个整数，表示所有的数。

输入输出样例 #1

输入 #1

2 2 1 1 2 1 2 1 2

输出 #1

1

说明/提示

• 对于30% 的数据，1 ≤ N ≤ 10 ; 1 ≤ M ≤ 4 1 \le N \le 10; 1 \le M \le 41≤N≤10;1≤M≤4；

• 对于60% 的数据，1 ≤ N ≤ 200 ; 1 ≤ M ≤ 200 1 \le N \le 200; 1 \le M \le 2001≤N≤200;1≤M≤200；

• 对于100% 的数据，1 ≤ N ≤ 5000 ; 1 ≤ M ≤ 5000 1 \le N \le 5000; 1 \le M \le 50001≤N≤5000;1≤M≤5000。

C++实现

#include<iostream>#include<cstdio>#include<vector>usingnamespacestd;constintmod=1e9+7;constintN=5001;intn,m,f[N][N],dp[N];vector<int>a[N];voiddfs(intx,intfa){intlen=a[x].size();for(inti=0;i<len;i++){if(a[x][i]==fa)continue;dfs(a[x][i],x);for(intj=1;j<=m;j++)f[x][j]=(1ll*f[x][j]*(dp[a[x][i]]-f[a[x][i]][j])%mod+mod)%mod;}for(inti=1;i<=m;i++)dp[x]+=f[x][i],dp[x]%=mod;}intmain(){scanf("%d%d",&n,&m);for(inti=1;i<=n;i++){intk;scanf("%d",&k);for(intj=1;j<=k;j++){intx;scanf("%d",&x);f[i][x]=1;}}for(inti=1;i<n;i++){intx,y;scanf("%d%d",&x,&y);a[x].push_back(y);a[y].push_back(x);}dfs(1,0);printf("%d",dp[1]);return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容