题解 CF997C 【Sky Full of Stars】

大家好像都是考虑容斥,咱这里有个不需要费脑子的二项式反演……

题意 :

有一个正方形网格,用三种颜色染。

求有多少种方案使得至少一行或一列是同一种颜色。

结果对大质数取模。

按照套路:

令F(i,j)为钦定有i行j列是同种颜色,其余任意的方案数。

令G(i,j)为恰好有i行j列是同种颜色的方案数。

我们要求的就是 : 全集-G(0,0)

容易得到F(x,y)=\sum\limits_{i=x}^n\sum\limits_{j=y}^n\dbinom{i}{x}\dbinom{j}{y}G(i,j)

然后采用高维二项式反演(请见Link):

G(x,y)=\sum\limits_{i=x}^n\sum\limits_{j=y}^n(-1)^{i+j-x-y}\dbinom{i}{x}\dbinom{j}{y}F(i,j)

再来算F(i,j),这需要分类讨论。

• 当两个参数都不为0时,所有被钦定的行和列必须是同种颜色。

F(i,j)=\dbinom{n}{i}\dbinom{n}{j}3*3^{(n-i)(n-j)}

即 : 选定行列 X 钦定颜色 X 放任自流

• 当任意一个参数为0时,被钦定的行或列不用一定是同种颜色。

F(i,0)=\dbinom{n}{i}3^i*3^{n(n-i)}

• 两个参数都为0

完全放任,F(0,0)=3^{n^2}

根据前面的反演:

G(0,0)=\sum\limits_{i=0}^n\sum\limits_{j=0}^n(-1)^{i+j}F(i,j)

再分三个部分求和:

• 当两个参数都不为0的贡献

=\sum\limits_{i=1}^n\sum\limits_{j=1}^n(-1)^{i+j}\dbinom{n}{i}\dbinom{n}{j}3*3^{(n-i)(n-j)} =3^{n^2+1}\sum\limits_{i=1}^n\sum\limits_{j=1}^n(-1)^{i+j}\dbinom{n}{i}\dbinom{n}{j}3^{-in-jn+ij} =3^{n^2+1}\sum\limits_{i=1}^n\dbinom{n}{i}(-1)^i3^{-in}\sum\limits_{j=1}^n\dbinom{n}{j}(-1)^{j}3^{-jn}3^{ij}

我们发现这个3^{ij}项十分讨厌,导致前后两个\sum有了关联,不能直接用二项式定理……

数据范围为10^6,只需要消掉一个\sum,还是有办法对付的。

=3^{n^2+1}\sum\limits_{i=1}^n\dbinom{n}{i}(-1)^i3^{-in}\sum\limits_{j=1}^n\dbinom{n}{j}(-1)^{j}3^{j(i-n)}

现在观察后面的\sum\limits_{j=1}^n\dbinom{n}{j}(-1)^{j}3^{j(i-n)}就可以二项式定理了。

this=\sum\limits_{j=1}^n\dbinom{n}{j}1^{n-j}(-3^{(i-n)})^{j}=(1-3^{(i-n)})^n-1

注意求和下标不到0,最后要减去1.

回代可得:

=3^{n^2+1}\sum\limits_{i=1}^n\dbinom{n}{i}(-1)^i3^{-in}((1-3^{(i-n)})^n-1)

快速幂就可以O(nlogn)计算了。

• 当某一个参数都为0的贡献

(其实是可以直接快速幂暴力,不过为了常数还是推一下式子吧) $=2\sum\limits_{i=1}^n(-1)^{i}\dbinom{n}{i}3^i*3^{n(n-i)} =2*3^{n^2}\sum\limits_{i=1}^n\dbinom{n}{i}(-1)^{i}3^i*3^{-in} =2*3^{n^2}\sum\limits_{i=1}^n\dbinom{n}{i}(-3^{(1-n)})^{i} - 两个参数都为0的贡献 $=3^{n^2}=$全集 又因为$ANS=$全集$-G(0,0)

我们发现,直接给前两部分贡献变号就能够得到答案了。

Code:

复杂度O(nlogn).

为了跑得快一点,使用了光速幂。

#include<algorithm>
#include<cstdio>
#define ll long long 
#define mod 998244353
#define tod 998244352
#define MaxN 1005000
using namespace std;
ll powM(ll a,int t)
{
  ll ans=1;
  while(t){
    if(t&1)ans=ans*a%mod;
    a=a*a%mod;
    t>>=1;
  }return ans;
}
int n;
ll fac[MaxN],ifac[MaxN],pw[35000],pw2[35000];
ll C(int n,int m)
{return fac[n]*ifac[m]%mod*ifac[n-m]%mod;}
ll pow3(int t)
{return pw2[t>>15]*pw[t&32767]%mod;}
void Init()
{
  fac[0]=ifac[0]=ifac[1]=1;
  for (int i=2;i<=n;i++)
    ifac[i]=(ifac[mod%i]*(mod-mod/i))%mod;
  for (int i=1;i<=n;i++){
    fac[i]=fac[i-1]*i%mod;
    ifac[i]=ifac[i]*ifac[i-1]%mod;
  }pw[0]=pw2[0]=1;
  for (int i=1;i<=32767;i++)
    pw[i]=pw[i-1]*3%mod;
  ll buf=pw[32767]*3%mod;
  for (int i=1;i<=31000;i++)
    pw2[i]=pw2[i-1]*buf%mod;
}
int main()
{
  scanf("%d",&n);
  Init();
  ll ans=0,sav;
  for (int i=1;i<=n;i++){
    sav=C(n,i)*pow3(1ll*(tod-i)*n%tod)%mod
       *(powM(1-pow3(i-n+tod),n)-1)%mod;
    if (i&1)ans=(ans-sav)%mod;
    else ans=(ans+sav)%mod;
  }ans=ans*pow3((1ll*n*n+1)%tod)%mod;
  ans=(ans+2*pow3(1ll*n*n%tod)%mod
          *(powM(1-pow3(tod+1-n),n)-1))%mod;
  printf("%I64d",(mod-ans)%mod);
  return 0;
}