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

cf997C. Sky Full of Stars(组合数 容斥)

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

题意

题目链接

\(n \times n\)的网格,用三种颜色染色,问最后有一行/一列全都为同一种颜色的方案数

Sol

Orz fjzzq

最后答案是这个

\[3^{n^2} - (3^n - 3)^n - \sum_{i = 1}^n (-1)^i C_n^i 3(3^{n-i} - 1)^n + (3^i - 3)(3^{(n-i)n}) \]

我来强行解释一波。

首先可以做个转化:答案 = 总的方案 - 任意行/列都至少含有两种颜色的方案

我们先来考虑列,任意一列含有两种颜色的方案是\((3^n-3)^n\)(-3是因为颜色相同的三种方案)。但是这样我们会多减去行合法的情况,因此还需要加一些方案,这些方案满足存在至少一行颜色都相同且任意一列至少含有两种颜色。

发现"至少"不太好搞,我们可以通过容斥把它变成"恰好",也就是加上恰好一行满足的,减去恰好两行满足的...。

那么对于这恰好\(i\)行满足条件的我们又需要来分类讨论。首先把他们选出来方案数是\(C_n^i\)

接下来就要分两种情况

  1. 选出来的\(i\)行的颜色(每行都是相同的h)有任意两个不同

这时候就简单了,方案数为\((3^i - 3) (3^{(n-i)n})\)。也就是减去每行颜色都相同的三种方案,剩下的随便选

  1. 选出来的\(i\)行的颜色两两相同

这时候对于每一列都有\((3^{n-i}-1)\)种方案,共有\(n\)列。同时这\(i\)行的颜色又有三种选发。

因此这时候的方案数为\(3(3^{n-i}-1)^n\)

然后大力算就行了

复杂度\(O(n \log n)\)

#include<bits/stdc++.h> 
#define Pair pair<int, int>
#define MP(x, y) make_pair(x, y)
#define fi first
#define se second
#define int long long 
#define LL long long 
#define Fin(x) {freopen(#x".in","r",stdin);}
#define Fout(x) {freopen(#x".out","w",stdout);}
using namespace std;
const int MAXN = 1e6 + 10, mod = 998244353, INF = 1e9 + 10;
const double eps = 1e-9;
template <typename A, typename B> inline bool chmin(A &a, B b){if(a > b) {a = b; return 1;} return 0;}
template <typename A, typename B> inline bool chmax(A &a, B b){if(a < b) {a = b; return 1;} return 0;}
template <typename A, typename B> inline LL add(A x, B y) {if(x + y < 0) return x + y + mod; return x + y >= mod ? x + y - mod : x + y;}
template <typename A, typename B> inline void add2(A &x, B y) {if(x + y < 0) x = x + y + mod; else x = (x + y >= mod ? x + y - mod : x + y);}
template <typename A, typename B> inline LL mul(A x, B y) {return 1ll * x * y % mod;}
template <typename A, typename B> inline void mul2(A &x, B y) {x = (1ll * x * y % mod + mod) % mod;}
template <typename A> inline void debug(A a){cout << a << '\n';}
template <typename A> inline LL sqr(A x){return 1ll * x * x;}
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, fac[MAXN], ifac[MAXN];
int fp(int a, int p) {
	int base = 1;
	while(p) {
		if(p & 1) base = mul(base, a);
		p >>= 1; a = mul(a, a);
	}
	return base;
}
int C(int N, int M) {
	return mul(fac[N], mul(ifac[M], ifac[N - M]));
}
signed main() {
	cin >> N;
	fac[0] = 1; for(int i = 1; i <= N; i++) fac[i] = mul(i, fac[i - 1]);
	ifac[N] = fp(fac[N], mod - 2);
	for(int i = N; i >= 1; i--) ifac[i - 1] = mul(ifac[i], i);
	int ans = add(fp(3, N * N), -fp(fp(3, N) - 3, N));
	for(int i = 1; i <= N; i++) {
		if(i & 1) {
			add2(ans, mul(C(N, i), add(mul(3, fp(fp(3, N - i) - 1, N)), mul(fp(3, i) - 3, fp(3, (N - i) * N)))));
		} else {
			add2(ans, -mul(C(N, i), add(mul(3, fp(fp(3, N - i) - 1, N)), mul(fp(3, i) - 3, fp(3, (N - i) * N)))));
		}
	}
	cout << ans;
	return 0;
}

鲜花

握手

雷人

路过

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

请发表评论

全部评论

专题导读
上一篇:
C语言极易出错的地方(更新中)发布时间:2022-07-13
下一篇:
C# 抓取页面(带认证) 转发布时间: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