当前位置：首页 > news >正文

Codeforces Round #439 (Div. 2) C.The Intriguing Obsession(组合数、记忆化搜索)

news 来源：原创 2024/4/29 8:01:38

题意：

给出a个红色点，b个蓝色点，c个紫色点，我们可以在这些点之间连任意数量长度为1的边，但是限制同颜色的点之间不能连边且同颜色的点之间的最短路径至少为3，求方案数% 998244353， a,b,c<=5000

思路：

分析最短路径至少为3代表当前颜色的点不能向其它两个颜色相同的点进行连边，并且每两组颜色之间的连边是不受另外一组颜色的影响的，所以最后把三种分组乘起来即可。那么对于一组(a,b)，其中a<=b，当前组的连边情况能连0,1,2...a条边，假如要连i条边，那么其选择就是C(m, 1)*C(m-1, 1)*..*C(m-i+1, 1)。再把所有连边情况加起来就是当前分组的所有情况，公式：Σ[i∈(0, a)]C(a, i)* (b!/(b-i)!)。

其实也可以用记忆化搜索做，内存恰好够。

代码1：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod = 998244353;
const int maxn = 5005;
ll fac[maxn], inv[maxn], fiv[maxn], ans, tmp;
void init()
{
	fac[0] = fac[1] = 1;
	inv[1] = 1;
	fiv[0] = fiv[1] = 1;
	for(int i = 2; i <= 5000; ++i)
	{
		fac[i] = fac[i-1]*i%mod;
		inv[i] = (-mod/i+mod)*inv[mod%i]%mod;
		fiv[i] = fiv[i-1]*inv[i]%mod;
	}
}
int main()
{
	int a, b, c, rx, ry;
	init(); ans = 1;
	cin >> a >> b >> c;
	rx = a, ry = b, tmp = 0;
	if(rx > ry) swap(rx, ry);
	for(int i = 0; i <= rx; ++i)
	{
		tmp += fac[rx]*fiv[i]%mod*fiv[rx-i]%mod*fac[ry]%mod*fiv[ry-i]%mod;
		tmp %= mod;
	}
	ans = ans*tmp%mod;
	
	rx = a, ry = c, tmp = 0;
	if(rx > ry) swap(rx, ry);
	for(int i = 0; i <= rx; ++i)
	{
		tmp += fac[rx]*fiv[i]%mod*fiv[rx-i]%mod*fac[ry]%mod*fiv[ry-i]%mod;
		tmp %= mod;
	}
	ans = ans*tmp%mod;
	
	rx = b, ry = c, tmp = 0;
	if(rx > ry) swap(rx, ry);
	for(int i = 0; i <= rx; ++i)
	{
		tmp += fac[rx]*fiv[i]%mod*fiv[rx-i]%mod*fac[ry]%mod*fiv[ry-i]%mod;
		tmp %= mod;
	}
	ans = ans*tmp%mod;
	
	cout << ans << endl;
	return 0;
}

代码2：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod = 998244353;
const int maxn = 5005;
ll dp[maxn][maxn];
ll work(int x, int y)
{
	if(!x || !y) return 1;
	if(dp[x][y]) return dp[x][y];
	return dp[x][y]=(work(x-1, y-1)*y%mod + work(x-1, y))%mod;
}
int main()
{
	int a, b, c;
	cin >> a >> b >> c;
	printf("%I64d\n", work(min(a, b), max(a, b))*work(min(a, c), max(a, c))%mod*work(min(b, c), max(b, c))%mod);
	return 0;
}

继续加油~