【题解】CF997C Sky Full of Stars

【题解】CF997C Sky Full of Stars

为什么我的容斥原理入门题是这道题？？？？？？？？？

\(Part-1\)正向考虑

直接考虑不合法合法的方案吧

所以我们设行有\(i\),列有\(j\)有是不同的颜色

所以分这几种情况讨论：

\[i\not=0,j\not=0
\\
i=j=0
\\
ij=0,i+j\not=0
\]

考虑到\(i=j=0​\)对答案没有贡献，所以我们考虑第一式和第三式吧

第三式简单一点，情况就是这样的：

方案数还是比较显然的(我说显然是因为是可以通过我努力思考得到，不是我可以秒杀...)

还要试推算一个容斥系数，最终就是

\[x_1= 2\times\Sigma_{i=1}^n (-1)^i C_n^i \times 3^i\times 3^{n(n-i)}
\]

第二式，情况就是这样的：

这种情况下，确定了一种就确定了所有颜色，枚举\(i,j​\)吧

\[x=\Sigma_{i=1}^n\Sigma_{j=1}^n (-1)^{j+i-1}3C_n^iC_n^j3^{(n-i)(n-j)}
\]

然而我们需要\(O(nlogn)\)所以我们考虑对式子变形一下，把所有(部分)\(i\)提出来

\[x=\Sigma_iC_n^i(-1)^{i-1}\Sigma_{j=1}^n C_n^j3^{(n-i)(n-j)}(-1)^j
\]

把\(j\)的拿出来二项式定理化一下，有些技巧性。

\[\Sigma_{j=1}^n C_n^j3^{(n-i)(n-j)}(-1)^j=-3^{n(n-i)}+\Sigma_{j=0}^n C_n^j3^{(n-i)(n-j)}(-1)^j
\\
=-3^{n(n-i)}+\Sigma_{j=0}^n C_n^j(3^{n-i})^{n-j}(-1)^j
\\
=-3^{n(n-i)}+(3^{n-i}-1)^n
\]

所以

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

于是答案就是

\[x_1+x_2= 2\times\Sigma_{i=1}^n (-1)^i C_n^i \times 3^i\times 3^{n(n-i)}+\Sigma_{i=1}^n C_n^i(-1)^{i-1}(-3^{n(n-i)}+(3^{n-i}-1)^n)
\]

复杂度\(O(nlogn)\)

呼呼呼 好难QAQ

\(part-2\)反向考虑

直接蒯了，有没有发现形式很相似？数学真奇妙hhh

给\(2​\)号代码吧

#include<bits/stdc++.h>

using namespace std;typedef long long ll;

#define RP(t,a,b) for(register int t=(a),edd=(b);t<=edd;++t)

#define DRP(t,a,b) for(register int t=(a),edd=(b);t>=edd;--t)

#define ERP(t,a) for(register int t=head[a];t;t=e[t].nx)

#define int long long

const int mod=998244353;

inline int ksm(int base,int p){register int ret=1;base%=mod;

    for(register int t=p;t;t>>=1,base*=base,base%=mod)if(t&1) ret*=base,ret%=mod;    return ret%mod;

}

const int maxn=1e6+5;

int fac[maxn];

int inv[maxn];

int ans;

int n;

inline int C(int n,int m){return (fac[n]*inv[m]%mod)*inv[n-m]%mod;}

signed main(){

#ifndef ONLINE_JUDGE

    freopen("A.in","r",stdin);

    freopen("A.out","w",stdout);

#endif

    cin>>n;

    inv[0]=fac[0]=1;

    RP(t,1,n) fac[t]=fac[t-1]*t%mod,inv[t]=inv[t-1]*ksm(t,mod-2LL)%mod;

    ans=ksm(3,n*n)%mod;

    ans=(ans-ksm(ksm(3,n)-3LL+mod,n)+mod)%mod;

    RP(t,1,n){

	register int q=C(n,t)*(3LL*ksm(ksm(3,n-t)-1LL,n)%mod+(ksm(3,n*(n-t))*((ksm(3,t)-3LL+mod)%mod))%mod)%mod;

	if(t&1) ans=(ans+q)%mod;

	else ans=((ans-q)%mod+mod)%mod;

    }

    ans=(ans%mod+mod)%mod;

    cout<<ans<<endl;

}