c/c++语言开发共享cf997C. Sky Full of Stars(组合数 容斥)

题意

题目链接

(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; }