codeforces 439 C - The Intriguing Obsession (和图有关的计数,组合数学)
题意:
3个岛屿群,每个岛屿群有若干岛屿。现在要在岛屿之间连桥,桥的长度是1,规定2个属于相同岛屿群的岛屿的距离要大于等于3.
思路:
一直在纠结大于等于3的距离的事情。。。其实这句话等价于,同一个岛屿,对于另外两个岛屿群,都最多只能连接1个岛屿。
那么其实,对于每一对岛屿群,是相互独立的。
对于任意一对岛屿群,设两边岛屿的数量分别为a,b
我们可以从两边各取0个,1个,最多取min(a,b)
需要注意的是,选取了端点之后有顺序的区别。
所以对于该对岛屿,答案是SUM{C[a][k] * C[b][k] * k!} (k属于0..min(a,b) )
对于其他 两对同理。
/* ***********************************************
Author :111qqz
Created Time :2017年10月25日 星期三 13时55分25秒
File Name :C.cpp
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define PB push_back
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const LL mod = 998244353;
const int N=5005;
LL C[N][N];
LL fac[N];
void init()
{
C[1][0] = C[1][1] = 1;
C[2][0] = C[2][2] = 1;
C[2][1] = 2;
for ( int i = 3 ; i < N ; i++)
{
for ( int j = 0 ; j <= i ; j++)
{
if (j==0)
C[i][j] = 1;
else C[i][j] = (C[i-1][j] + C[i-1][j-1])%mod;
}
}
fac[0] = fac[1] = 1;
for ( int i = 2 ; i < N ; i++) fac[i] = (fac[i-1] * i)%mod;
}
int a,b,c;
LL ans = 1;
int main()
{
#ifndef ONLINE_JUDGE
freopen("./in.txt","r",stdin);
#endif
init();
cin>>a>>b>>c;
LL cur = 0;
for ( int i = 0 ; i <= min(a,b) ; i++)
{
cur = ( cur + C[a][i] * C[b][i] % mod * fac[i] % mod) %mod;
}
ans = ans * cur % mod;
cur = 0 ;
for ( int i = 0 ; i <= min(a,c) ; i++)
cur = ( cur + C[a][i] * C[c][i] % mod * fac[i] % mod ) % mod;
ans = ans * cur % mod;
cur = 0 ;
for ( int i = 0 ; i <= min (b,c) ; i++)
cur = ( cur + C[b][i] * C[c][i] % mod * fac[i] % mod) %mod;
ans = ans * cur % mod;
cout<<ans<<endl;
#ifndef ONLINE_JUDGE
fclose(stdin);
#endif
return 0;
}