题目链接:

题意:n*n的格子,用3种颜色填涂,求至少一行或者一列颜色相同的方案数

题解:

　　第一想法肯定是容斥:

　　1.优先考虑只有行或者只有列的方案数:

　　\(2\sum_{i = 1}^{n}\left(-1 \right )^{i + 1}3^{i + n(n - i)}C_{n}^{i}\)

　　2.其次考虑既有行又有列的方案数,此时会发现这些行列的颜色是相同的

　　\(\sum_{i = 1}^{n}\sum_{j = 1}^{n}(-1)^{i + j + 1}C_{n}^{i}C_{n}^{j}3^{(n - i)(n - j) + 1}\)

　　化简替换:用n-i,n-j代替i,j

　　\(\sum_{i = 0}^{n - 1}\sum_{j = 0}^{n - 1}(-1)^{i + j + 1}C_{n}^{i}C_{n}^{j}3^{ij + 1}\)

　　最后化简得到:

　　\(\sum_{i = 0}^{n - 1}(-1)^{n + i + 1}C_{n}^{i}\sum_{j = 0}^{n - 1}(-1)^{n - j}C_{n}^{j}(3^{i})^{j}=3\sum_{i = 0}^{n - 1}(-1)^{i + 1}C_{n}^{i}\left [ \left ( 3^{i} - 1 \right )^{n} - 3^{ni} \right ]\)

 

#include
     
      using namespace std;const int N=1e6+10;typedef long long ll;const ll mod=998244353;ll fac[N],inv_fac[N];ll qpow(ll a,ll b){    ll res=1,tmp=a;    for(;b;b>>=1,(tmp*=tmp)%=mod)         if(b&1) (res*=tmp)%=mod;    return res;}void init(){    fac[0]=1;    for(int i=1;i
      
       =0;i--) inv_fac[i]=inv_fac[i+1]*(i+1)%mod; }ll C(int n,int m){    return (fac[n]*inv_fac[n-m]%mod)*inv_fac[m]%mod;}ll add(ll a,ll b) {    a=(a+b)%mod;    if(a<0) return a+mod;    return a;}int main(){    int n;scanf("%d",&n);init();ll ans=0;    if(n==1){printf("3\n");return 0;}    int s=1;    ll pow3=1;    ll p3n = qpow(3, n);    for(ll i=1;i<=n;i++,s*=-1){        ll tmp=s*C(n,i)*qpow(3,i)%mod*qpow(3,n*(n-i)%(mod-1))%mod;        ans=add(ans,tmp);     }    ans=add(ans,ans);     s=(n&1)?1:-1;    for(ll i=0;i