[CF997C] Sky Full of Stars

\(\text{Problem}:\)

\(\text{Solution}:\)

答案即总方案数减去没有一行或一列是同种颜色的方案数。

设 \(f_{i,j}\) 表示恰好有 \(i\) 行 \(j\) 列是同种颜色的方案数，\(g_{i,j}\) 表示钦定有 \(i\) 行 \(j\) 列是同种颜色的方案数，有：

\[\begin{aligned} g_{i,j}&=\binom{n}{i}\binom{n}{j}3^{(n-i-j)n+ij+1},i\geq 1,j\geq 1\g_{0,j}&=\binom{n}{j}3^{(n-j)n+j},i=0\g_{i,0}&=\binom{n}{i}3^{(n-i)n+i},j=0\f_{i,j}&=\sum\limits_{x=i}^{n}\sum\limits_{y=j}^{n}(-1)^{x+y-i-j}\binom{x}{i}\binom{y}{j}g_{x,y} \end{aligned} \]

要求的显然为 \(f_{0,0}\)，考虑把答案分成三部分计算。\(i=0\) 和 \(j=0\) 的部分可以暴力计算，下面只考虑 \(i\geq 1,j\geq 1\) 的情况，有：

\[\begin{aligned} f_{0,0}&=res+\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}(-1)^{i+j}\binom{n}{i}\binom{n}{j}3^{(n-i-j)n+ij+1}\&=res+3\sum\limits_{i=1}^{n}(-1)^{i}\binom{n}{i}\left(\sum\limits_{j=0}^{n}(-1)^{j}\binom{n}{j}3^{(n-i)(n-j)}-3^{n(n-i)}\right)\&=res+3\sum\limits_{i=1}^{n}(-1)^{i}\binom{n}{i}((3^{n-i}-1)^{n}-3^{n(n-i)})\ans&=3^{n^2}-f_{0,0} \end{aligned} \]

总时间复杂度 \(O(n\log n)\)。

\(\text{Code}:\)

#include 
#pragma GCC optimize(3)
#define int long long
#define ri register
#define mk make_pair
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define is insert
#define es erase
#define vi vector
#define vpi vector>
using namespace std; const int N=1000010, Mod=998244353;
inline int read()
{
	int s=0, w=1; ri char ch=getchar();
	while(ch<‘0‘||ch>‘9‘) { if(ch==‘-‘) w=-1; ch=getchar(); }
	while(ch>=‘0‘&&ch<=‘9‘) s=(s<<3)+(s<<1)+(ch^48), ch=getchar();
	return s*w;
}
int n,pw[N+5],fac[N+5],inv[N+5];
inline int ksc(int x,int p) { int res=1; for(;p;p>>=1, x=1ll*x*x%Mod) if(p&1) res=1ll*res*x%Mod; return res; }
inline int C(int x,int y) { if(x