题解 CF997C 【Sky Full of Stars】
command_block
2019-10-27 20:27:32
大家好像都是考虑容斥,咱这里有个不需要费脑子的二项式反演……
------------
**题意** :
有一个正方形网格,用三种颜色染。
求有多少种方案使得**至少**一行或一列是同一种颜色。
结果对大质数取模。
按照套路:
令$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](https://www.luogu.org/blog/command-block/yi-suo-ji-guai-di-fan-yan)):
$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的贡献
$i,j$为0本质相同,我们不妨只计$i$,然后贡献翻倍即可。
(其实是可以直接快速幂暴力,不过为了常数还是推一下式子吧)
$=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}$
$=2*3^{n^2}((1-3^{(1-n)})^n-1)$(注意这里求和下标也不到0)
- 两个参数都为0的贡献
$=3^{n^2}=$全集
又因为$ANS=$全集$-G(0,0)$
我们发现,直接给前两部分贡献变号就能够得到答案了。
------------
**Code:**
复杂度$O(nlogn)$.
为了跑得快一点,使用了光速幂。
```cpp
#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;
}
```