题目
解法
令 \(f(x,y)\) 为钦定 \(x\) 行 \(y\) 列为同种颜色的方案数，\(g(x,y)\) 为恰好 \(x\) 行 \(y\) 列为同种颜色的方案数，可以想到，当 \(x,y>0\) 时，\(x\) 行 \(y\) 列必须是同种颜色。答案就是 \(3^{n^2}-g(0,0)\)。
那么由高维二项式反演有：
\[f(x,y)=\sum_{i=x}^n\sum_{j=y}^n \binom{i}{x}\binom{j}{y}g(i,j) \] \[g(x,y)=\sum_{i=x}^n\sum_{j=y}^n (-1)^{i-x+j-y}\binom{i}{x}\binom{j}{y}f(i,j) \] \[g(0,0)=\sum_{i=0}^n\sum_{j=0}^n (-1)^{i+j}f(i,j) \]大力分类讨论：
-
\(x,y>0\)。\(f(x,y)=\binom{n}{x}\binom{n}{y}\cdot 3\cdot 3^{(n-x)(n-y)}\)。
\[\text{Ans}_1=\sum_{i=1}^n\sum_{j=1}^n (-1)^{i+j}\binom{n}{i}\binom{n}{j}\cdot 3\cdot 3^{(n-i)(n-j)} \] \[=3^{n^2+1}\sum_{i=1}^n (-1)^i\binom{n}{i}3^{-ni}\sum_{j=1}^n (-3^{i-n})^j\binom{n}{j} \] \[=3^{n^2+1}\sum_{i=1}^n (-1)^i\binom{n}{i}3^{-ni}((1-3^{i-n})^n-1) \] -
\(xy=0\) 且 \(x+y\neq 0\)。不妨设 \(y=0\)。\(f(x,0)=\binom{n}{x}\cdot 3^i\cdot 3^{(n-x)n}\)
\[\text{Ans}_2=2\sum_{i=1}^n (-1)^{i}f(i,0) \] \[=2\sum_{i=1}^n (-1)^{i}\binom{n}{i}\cdot 3^i\cdot 3^{(n-i)n} \]到这里就可以了，不过你还可以去掉一个 \(\sum\)：
\[=2\cdot 3^{n^2}((1-3^{1-n})^n-1) \] -
\(x+y=0\)。\(\text{Ans}_3=f(0,0)=3^{n^2}\)。
代码
#include <cstdio>
#define print(x,y) write(x),putchar(y)
template <class T>
inline T read(const T sample) {
T x=0; char s; bool f=0;
while((s=getchar())>'9' or s<'0')
f|=(s=='-');
while(s>='0' and s<='9')
x=(x<<1)+(x<<3)+(s^48),
s=getchar();
return f?-x:x;
}
template <class T>
inline void write(const T x) {
if(x<0) {
putchar('-'),write(-x);
return;
}
if(x>9) write(x/10);
putchar(x%10^48);
}
const int mod=998244353,maxn=1e6+5;
const int phi=mod-1;
int n,inv[maxn];
int qkpow(int x,int y) {
int r=1;
while(y) {
if(y&1) r=1ll*r*x%mod;
x=1ll*x*x%mod; y>>=1;
}
return r;
}
int main() {
n=read(9);
int C=1,ans=0,tmp;
inv[1]=1;
for(int i=2;i<=n;++i)
inv[i]=(mod-1ll*mod/i*inv[mod%i]%mod)%mod;
for(int i=1;i<=n;++i) {
C=1ll*C*(n-i+1)%mod*inv[i]%mod;
tmp=1ll*C*qkpow(3,phi-1ll*n*i%phi)%mod*(qkpow(1-qkpow(3,(i-n+phi)%phi)+mod,n)-1+mod)%mod;
if(i&1) ans=(ans+tmp)%mod;
else ans=(ans-tmp+mod)%mod;
}
ans=1ll*ans*qkpow(3,(1ll*n*n+1)%phi)%mod;
ans=(ans-2ll*qkpow(3,1ll*n*n%phi)%mod*(qkpow(1-qkpow(3,phi-n+1)+mod,n)-1+mod)%mod+mod)%mod;
print(ans,'\n');
return 0;
}