在线时间:8:00-16:00
迪恩网络APP
随时随地掌握行业动态
扫描二维码
关注迪恩网络微信公众号
题目链接:http://codeforces.com/contest/869/problem/C 题目大意: 有三种颜色(红蓝紫)的点 \(a, b, c\) 个,这些点之间可以用距离为\(1\)的边连接(也可以不连接)。规定同种颜色的点之间要么不连接,否则它们之间的距离必须大于或等于\(3\)。问有多少种连接方式。 知识点: 组合计数 解题思路: 显然,对于一种颜色的点,它只能与另外两种颜色的点直接连接。于是我们可以将问题分成三部分:红点与蓝点直接连接、蓝点与紫点直接连接、紫点与红点直接连接。求出三个部分的方案数,三者相乘即为答案。 对于每个部分,设其两种色点数分别为 \(x\) 和 \(y\),\(k=min(x,y)\),则该部分的方案数为:\(\sum_{i=0}^{i=k} i!C_{x}^{i}C_{y}^{i}\). (对于这条式子的解释:两种色点之间能够连 \(0\) ~ \(k\) 条边,所以枚举 \(i=0\) 到 \(i=k\) 在两种色点中各选 \(i\) 个点的方案数为 \(C_{x}^{i}C_{y}^{i}\),而这两边的色点匹配的方案数为 \(i!\)). AC代码: 1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const ll mod = 998244353; 5 const int maxn = 5003; 6 ll C[maxn][maxn],jie[maxn]; 7 void init(){ 8 C[0][0]=C[1][0]=C[1][1]=1; 9 for(int i=2;i<maxn;i++){ 10 C[i][0]=C[i][i]=1; 11 for(int j=1;j<i;j++) 12 C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod; 13 } 14 jie[0]=1; 15 for(ll i=1;i<maxn;i++) jie[i]=jie[i-1]*i%mod; 16 } 17 int main(){ 18 init(); 19 ll a,b,c; 20 scanf("%lld%lld%lld",&a,&b,&c); 21 ll ans1=0,ans2=0,ans3=0; 22 ll t; 23 t=min(a,b); 24 for(ll i=0;i<=t;i++) ans1=(ans1+C[a][i]*C[b][i]%mod*jie[i]%mod)%mod; 25 t=min(b,c); 26 for(ll i=0;i<=t;i++) ans2=(ans2+C[b][i]*C[c][i]%mod*jie[i]%mod)%mod; 27 t=min(a,c); 28 for(ll i=0;i<=t;i++) ans3=(ans3+C[a][i]*C[c][i]%mod*jie[i]%mod)%mod; 29 30 printf("%lld\n",(ans1*ans2%mod)*ans3%mod); 31 }
|
2023-10-27
2022-08-15
2022-08-17
2022-09-23
2022-08-13
请发表评论