• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

CF869CTheIntriguingObsession

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

题目链接: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 }

 

  


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
C#屏蔽Alt+F4组合键发布时间:2022-07-13
下一篇:
重新启动C++Builder发布时间:2022-07-13
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap