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
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define PB push_back
14#define fst first
15#define sec second
16#define lson l,m,rt<<1
17#define rson m+1,r,rt<<1|1
18#define ms(a,x) memset(a,x,sizeof(a))
19typedef long long LL;
20#define pi pair < int ,int >
21#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const LL mod = 998244353;
7const int N=5005;
8LL C[N][N];
9LL fac[N];
10void init()
11{
12 C[1][0] = C[1][1] = 1;
13 C[2][0] = C[2][2] = 1;
14 C[2][1] = 2;
15 for ( int i = 3 ; i < N ; i++)
16 {
17 for ( int j = 0 ; j <= i ; j++)
18 {
19 if (j==0)
20 C[i][j] = 1;
21 else C[i][j] = (C[i-1][j] + C[i-1][j-1])%mod;
22 }
23 }
24 fac[0] = fac[1] = 1;
25 for ( int i = 2 ; i < N ; i++) fac[i] = (fac[i-1] * i)%mod;
26}
27int a,b,c;
28LL ans = 1;
29int main()
30{
31 #ifndef ONLINE_JUDGE
32 freopen("./in.txt","r",stdin);
33 #endif
34 init();
35 cin>>a>>b>>c;
36 LL cur = 0;
37 for ( int i = 0 ; i <= min(a,b) ; i++)
38 {
39 cur = ( cur + C[a][i] * C[b][i] % mod * fac[i] % mod) %mod;
40 }
41 ans = ans * cur % mod;
42 cur = 0 ;
43 for ( int i = 0 ; i <= min(a,c) ; i++)
44 cur = ( cur + C[a][i] * C[c][i] % mod * fac[i] % mod ) % mod;
45 ans = ans * cur % mod;
46 cur = 0 ;
47 for ( int i = 0 ; i <= min (b,c) ; i++)
48 cur = ( cur + C[b][i] * C[c][i] % mod * fac[i] % mod) %mod;
49 ans = ans * cur % mod;
50 cout<<ans<<endl;
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}