时间限制：1s 空间限制：512MB
二分图又称作二部图，是图论中的一种特殊模型。 设 是一个无向图，如果顶点 可分割为两个互不相交的子集 ，并且图中的每条边 所关联的两个顶点 和 分别属于这两个不同的顶点集 和 ，则称图 为一个二分图。
我们也可以说，图 为二分图，当且仅当顶点 可分割为两个互不相交的子集 ，并且 同集合中任意两点最短路长度不小于 。
由此定义三分图如下：设 是一个无向图，如果顶点 可分割为三个互不相交的子集，并且同集合中任意两点最短路长度不小于 ，则称图 为由点集 构成的三分图。
现在你来到了一片群岛，群岛被分成上述的 三部分。你打算在它们之间修建桥梁，使得构成的图是一个三分图(任何两个岛屿是互不相同的)。请求出方案数对 取模的结果。
第一行：一个整数 ，表示数据组数。 接下来 行，每行三个整数 a, b, c.分别为三个点集的大小。
每组数据输出一行，表示该组数据的答案。
3
1 1 1
1 2 2
6 2 9
样例输出
8
63
813023575
数据范围与提示
对于20% 的数据，a, b, c <= 4；
对于包括50%以上的 的数据，T <= 500 ；
对于100%的数据 1<= a, b, c <3000, 1 <= T <= 200000。
题解：
首先， 容易得到的结论：设三个集合为a, b, c， 每两个集合(如a， b)的情况方案总数为get_sum(a, b);
根据乘法原理，则答案为get_sum(a, b) * get_sum(a, c) * get_sum(b, c);
则可以讨论每两个集合之间的关系；
因集合中每两点最小距离 >= 3， 所以每个集合的一个点只能向另一个集合连出一条边；
设f[i][j] 为集合i，j之间的方案总数， 考虑新加一个点的贡献，
则有f[i][j] = f[i][j-1] + i * f[i-1][j-1];
直接DP即可， 注意每步一取模。
code：
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long LL;
const LL mod = 998244353;
LL read() {
LL x = 0, f = 1; char ch = getchar();
while(! isdigit(ch)) f = (ch==‘-‘)?-1:1, ch = getchar();
while(isdigit(ch)) x = (x<<3)+(x<<1)+(ch^48), ch = getchar();
return x * f;
}
LL t, a, b, c;
LL ans, f[3005][3005];
int main() {
t = read();
f[1][1] = 2;
for(int i = 1;i <= 3000;i ++) f[1][i] = f[i][1] = i + 1;
for(int i = 2;i <= 3000;i ++)
for(int j = 2;j <= 3000;j ++)
(f[i][j] = f[i][j-1] + (i * f[i-1][j-1]) % mod) %= mod;
while(t --> 0) {
a = read(); b = read(); c = read();
ans = ((f[a][b] * f[a][c]) % mod) * f[b][c] % mod;
printf("%lld\n", ans);
}
return 0;
}
补充：
特别的， 考虑 若此题 T == 1 ，1 <= a, b, c <= 1e7;
若DP的话， --MLE~， 直接考虑连 i 条边时 对答案的贡献可知
C为组合数， A为排列数。
i == 0， ans0 = C(n, 0) * A(m, 0);
i == 1， ans1 = C(n, 1) * A(m, 1);
~~~~~~~~~~~~~~~~~~~~~~~~~~
i == min(n, m), ans_min(n, m) = C(n, min(n, m)) * A(m, min(n, m));
则get_sum(n, m) = ans0 + ans1 + --- + ans_min(n, m);
O(n) 预处理阶乘， 费马小定理求逆元(998244353为质数)。
就可以了。
其实， 这是我考试时的写法。 当时考虑到数据组数过多， 空间换时间， 加了一个优化，可还是挂了。
要不是数据原因 ， 正解是DP， 我就完虐DP了~~
code：
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long LL;
const LL mod = 998244353;
LL read() {
LL x = 0, f = 1; char ch = getchar();
while(! isdigit(ch)) f = (ch==‘-‘)?-1:1, ch = getchar();
while(isdigit(ch)) x = (x<<3)+(x<<1)+(ch^48), ch = getchar();
return x * f;
}
LL t, a, b, c;
LL ans, ans1, ans2, ans3, fac[10000006];
inline LL ksm(LL x, LL y) {
LL res = 1;
for( ; y ;x = x * x % mod, y >>= 1)
if(y & 1) res = res * x % mod;
return res;
}
inline LL C(LL n, LL m) { return (fac[n] * ksm(fac[n-m], mod-2))% mod * ksm(fac[m], mod-2) % mod; }
inline LL A(LL n, LL m) { return fac[n] * ksm(fac[n-m], mod-2) % mod ; }
inline LL getsum(LL x, LL y) {
LL minl = min(x, y), ans = 0;
for(int i = 0;i <= minl;i ++)
(ans += C(x, i) * A(y, i) % mod) %= mod;
return ans;
}
int main() {
t = read();
fac[0] = fac[1] = 1;
for(int i = 2;i <= 10000005;i ++) fac[i] = fac[i-1] * i % mod;
while(t --> 0) {
a = read(); b = read(); c = read();
ans1 = getsum(a, b);
ans2 = getsum(b, c);
ans3 = getsum(a, c);
ans = ((ans1 * ans2) % mod) * ans3 % mod;
printf("%lld\n", ans);
}
return 0;
}
完结~
原文：https://www.cnblogs.com/Paranoid-LS/p/11256889.html